내 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, min;
static ArrayList<int[]> home, chicken;
static int[] distance;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
home = new ArrayList<>();
chicken = new ArrayList<>();
min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int x = Integer.parseInt(st.nextToken());
if (x == 2) {
chicken.add(new int[] { i, j });
} else if (x == 1) {
home.add(new int[] { i, j });
}
}
}
distance = new int[home.size()];
Arrays.fill(distance, 100);
dfs(-1, 0);
System.out.println(min);
}
static void dfs(int index, int count) {
if (count > M) {
return;
}
min = Math.min(min, Arrays.stream(distance).sum());
int[] temp = distance.clone();
for (int i = index + 1; i < chicken.size(); i++) {
for (int j = 0; j < home.size(); j++) {
int x = Math.abs(chicken.get(i)[0] - home.get(j)[0]) + Math.abs(chicken.get(i)[1] - home.get(j)[1]);
distance[j] = Math.min(distance[j], x);
}
dfs(i, count + 1);
distance = temp.clone();
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
강의실 배정 - 11000번 (0) | 2022.02.28 |
---|---|
찾기 - 1786번 (0) | 2022.02.24 |
아기 상어 - 16236번 (0) | 2022.02.23 |
감시 - 15683번 (0) | 2022.02.18 |
빵집 - 3109번 (0) | 2022.02.17 |