주의할 점은... visit 체크를 할 때 다음칸이 0이 아니라고 해서 지나가지 말고 다음칸에 이동했을 때 time 이 더 작은 경우는 갱신을 해줘야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.function.BiFunction;
public class Main {
private static int n;
private static int m;
private static int[][] map;
private static List<Node> virusList;
private static List<Integer> tmp = new ArrayList<>();
private static int ans = 987654321;
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());
map = new int[n][n];
virusList = new ArrayList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 2) {
//바이러스가 올 수 있는 자리
virusList.add(new Node(i, j, 1));
}
}
}
dfs(0);
if(ans == 987654321) ans = 0;
System.out.println(ans - 1);
}
private static void dfs(int startIdx ){
if (tmp.size() == m) {
//이제 여기서 bfs 를 돌리면 되자나
int res = bfs();
if(res == -1) return;
if (res< ans) {
ans = res;
}
return;
}
for (int i = startIdx; i < virusList.size(); i++) {
tmp.add(i);
dfs(i + 1);
tmp.remove(tmp.size() - 1);
}
}
private static int bfs(){
int[][] visit = new int[n][n];
Queue<Node> q = new LinkedList<>();
for (int i = 0; i < tmp.size(); i++) {
Node virus = virusList.get(tmp.get(i));
q.add(virus);
visit[virus.y][virus.x] = 1;
}
int[] dy = {0, 0, 1, -1};
int[] dx = {1, -1, 0, 0};
int result = -1;
while (!q.isEmpty()) {
Node cur = q.poll();
if(cur.time > result)
result = cur.time;
for (int i = 0; i < 4; i++) {
int ny = cur.y + dy[i];
int nx = cur.x + dx[i];
if(ny < 0 || nx < 0 || ny >=n || nx >= n) continue;
if(map[ny][nx] == 1) continue;
if(visit[ny][nx] !=0 && visit[ny][nx] <= cur.time + 1) continue;
visit[ny][nx] = cur.time + 1;
q.add(new Node(ny, nx, cur.time + 1));
}
}
//모든곳이 다 찼는지 확인
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visit[i][j] != 0 || map[i][j] == 1) cnt++;
}
}
if(cnt == n*n) return result;
else return -1;
}
private static class Node {
int y;
int x;
int time;
Node(int y, int x , int time){
this.y = y;
this.x = x;
this.time = time;
}
}
}