문제에서 요구하는 답은 도시에 있는 치킨집 M개를 고르는데 가장 거리가 짧은 치킨 거리를 구하는 것이다. 가장 거리가 짧은 거리를 구하는데 DFS 로 풀기위해서는 갈 수 있을만큼 최대로 많이 가고 갈수 없으면 이전 정점으로 돌아가는 방법을 사용한다. 모든 치킨집을 한번씩 방문 하여야 한다. 그래서 방문 여부를 확인 할 수 있는 배열을 선언하여 flag 값으로 두어 이전 값과 구분을 한다.
chicken = new ArrayList<>();
person = new ArrayList<>();
map = new int[n][n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 1) { // 집
person.add(new Map(i, j));
} else if (map[i][j] == 2) { // 치킨집
chicken.add(new Map(i, j));
}
}
}
/**
* 백트레킹
*
* @param start 시작점
* @param count 치킨 매장
*/
public static void dfs(int start, int count) {
if (count == m) {
// m 개의 매장이 되었을때에 가장 짧은 거리
}
// 치킨집의 개수만큼 백트래킹을 한다
for (int i = start; i < chicken.size(); i++) {
visited[i] = true;
dfs(i + 1, count + 1);
visited[i] = false;
}
}
int length = 0;
for (int i = 0; i < person.size(); i++) {
int temp = Integer.MAX_VALUE; // 범위 넘는 경우 방지
for (int j = 0; j < chicken.size(); j++) {
if (visited[j]) {
int distance = Math.abs(person.get(i).x - chicken.get(j).x)
+ Math.abs(person.get(i).y - chicken.get(j).y);
temp = Math.min(temp, distance);
}
}
length += temp;
}
answer = Math.min(answer, length);
return;
연습을 더 많이 해봐야 더 와닿을 것 같다. 여기저기 많이 응용되는 부분이 많다. 차이점을 명확하게 알고 풀면 더 좋을 것 같다