A. 문제설명
https://www.acmicpc.net/problem/15686
문제에 대한 자세한 설명은 링크 참조
1. N * N 배열 크기의 도시가 존재
2. 배열의 각 좌표에는 0: 빈칸, 1: 집, 2: 치킨집이 존재
3. 각 집에서 가장 가까운 치킨집의 거리를 '치킨거리'라고 하는데, 이는 |r1-r2| + |c1-c2|로 구한다.
4. 여기서, 주어진 치킨집 중 M개의 치킨집만을 남기고 폐업하려고 하는데, 그 조건은 남은 M개의 치킨집이 도시의 모든 집들의 치킨거리가 최소가 되는 경우이다.
5. M개의 치킨집을 살렸을 때 도시의 최소치킨거리를 구할 것
B. 접근법
먼저 이 문제에서 내가 생각한 방식은 DFS이다. M개의 치킨집을 살리는 것에 대한 조합을 DFS로 모두 구해야하고, 그 조합을 모두 구했을 때 각각의 도시치킨 거리를 구한다. 그 중에서 가장 최소의 것을 반환하면 된다.
C. 풀이
1. 먼저 DFS로 M개의 치킨집 조합을 구한다. 나의 경우 치킨집의 좌표를 Pair 자료형의 벡터로 선언했기 때문에 벡터의 인덱스 조합을 먼저 구했다.
2. M개의 벡터 인덱스 조합이 구해진 DFS의 베이스케이스에서 도시치킨거리를 구한다.
3. 각 도시의 치킨거리는 각 집들의 최소치킨거리를 더한 합이다.
D. 내 코드
