문제
해결 방법
- 백트래킹을 활용하여 치킨집을 M개 선택한다.
- 각 집에서 가장 가까운 치킨집과의 거리를 계산한다.
- 모든 집에서 가장 가까운 치킨집의 거리를 더해 결과와 비교하여 갱신한다.
정답 코드 - JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int M;
static int ret = Integer.MAX_VALUE;
static int[][] arr;
static int[] find;
static boolean[] visited;
static ArrayList<Pair> home = new ArrayList<>();
static ArrayList<Pair> chicken = new ArrayList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 2) {
chicken.add(new Pair(i, j));
} else if (arr[i][j] == 1) {
home.add(new Pair(i, j));
}
}
}
find = new int[M];
visited = new boolean[chicken.size()];
backtracking(0);
bw.write(String.valueOf(ret));
bw.flush();
}
static void backtracking(int k) {
if (k == M) {
int[][] map = new int[N][N];
int max = 0;
for (int i : find) {
Pair get = chicken.get(i);
for (Pair home : home) {
int tmp = Math.abs(get.x - home.x) + Math.abs(get.y - home.y);
if (map[home.x][home.y] == 0) {
map[home.x][home.y] = tmp;
} else {
map[home.x][home.y] = Math.min(tmp, map[home.x][home.y]);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
max += map[i][j];
}
}
ret = Math.min(ret, max);
return;
}
int start = 0;
if (k > 0) {
start = find[k - 1];
}
for (int i = start; i < chicken.size(); i++) {
if (!visited[i]) {
visited[i] = true;
find[k] = i;
backtracking(k + 1);
visited[i] = false;
}
}
}
static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
오늘의 회고
백트래킹을 활용하면 항상 코드가 지저분해지는 것 같다. 깔끔한 백트래킹 코드에 대해 한번 공부해 봐야겠다.