[boj] 연구소 3_17142 JAVA

문제 캡처

 

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static class Loc {
        int r, c;
        
        Loc(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    static List<Loc> viruses = new ArrayList<>();
    static int N, M, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}, arr[][];
    static boolean[][] visited;
    static int minTime = Integer.MAX_VALUE;
    static int emptyCount = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.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(bf.readLine());
            for(int j=0;j<N;j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 2) {
                    viruses.add(new Loc(i, j));
                } else if(arr[i][j] == 0) {
                    emptyCount++;
                }
            }
        }

        activateVirus(-1, 0, new int[M]);
        System.out.println(minTime == Integer.MAX_VALUE ? -1 : minTime);
    }

    private static void activateVirus(int index, int cnt, int[] selected) {
        if(cnt == M) {
            getTime(selected);
            return;
        }

        for(int i=index+1;i<viruses.size();i++) {
            selected[cnt] = i;
            activateVirus(i, cnt+1, selected);
        }
    }

    private static void getTime(int[] selected) {
        Queue<Loc> queue = new ArrayDeque<>();
        visited = new boolean[N][N];
        int[][] times = new int[N][N];
        int infected = 0;
        int maxTime = 0;

        // 선택된 바이러스 위치 큐에 넣기
        for(int i : selected) {
            Loc virus = viruses.get(i);
            queue.offer(virus);
            visited[virus.r][virus.c] = true;
        }

        while(!queue.isEmpty()) {
            Loc cur = queue.poll();
            
            for(int d=0;d<4;d++) {
                int nx = cur.r + dx[d];
                int ny = cur.c + dy[d];
                
                if(isInRange(nx, ny) && !visited[nx][ny] && arr[nx][ny] != 1) {
                    visited[nx][ny] = true;
                    times[nx][ny] = times[cur.r][cur.c] + 1;
                    queue.offer(new Loc(nx, ny));
                    
                    if(arr[nx][ny] == 0) {
                        infected++;
                        maxTime = Math.max(maxTime, times[nx][ny]);
                    }
                }
            }
        }

        // 모든 빈 칸이 감염되었는지 확인
        if(infected == emptyCount) {
            minTime = Math.min(minTime, maxTime);
        }
    }

    private static boolean isInRange(int i, int j) {
        return 0 <= i && i < N && 0 <= j && j < N;
    }
}