[BOJ15686] 치킨 배달

치킨 거리가 가장 작은 값

• 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리
• 거리는 맨해튼 거리(https://en.wikipedia.org/wiki/Taxicab_geometry) 사용
• 0 빈 칸, 1 집, 2 치킨집
• 가장 수익을 많이 낼 수 있는 치킨집 M개 뽑기(치킨 거리 최소)

입력

• N(2<= <=50), M(1<= <=13)
• 도시 정보 2차원 배열

출력

• M개의 치킨집을 골랐을 때, 치킨 거리의 최소 값

설계

• 집, 치킨 집을 배열에 따로 저장
• 치킨 집 중 M개 뽑기
• 집을 기준으로 M개 뽑은 치킨집과의 최소 거리 구하기
• 각 집의 최소 거리 다 더하면 치킨 거리
• M개의 경우의 수의 치킨 거리 모두 구해서 최소 값 출력

피드백

• 치킨 집을 M개 뽑을 때, 백트래킹을 이용한 순열을 구현했더니 시간초과 발생
• 백트래킹을 이용한 조합으로 수정
• 순열과 달리 조합을 이용할 때는, dfs 재귀함수 매개변수로 반복문의 index 값을 추가하여, 이전에 사용한 값은 다시 방문하지 않는 방식으로 접근

How I solved(click to github)

---

ref :
BOJ15686