[백준 17142] 연구소(Java)

문제 링크 : https://www.acmicpc.net/problem/17142

이 문제는 bfs와 백트래킹을 이용하여 풀 수 있습니다.

우선 바이러스가 활성화될 수 있는 여러 위치들 중 M개만 활성화시켜야 하기 때문에 백트래킹을 이용하여 M개를 선택합니다. 그 후 활성화시킨 바이러스에서 bfs 탐색을 진행하여 0이 없을 경우 그 카운트 값의 최솟값을 계속 갱신합니다.

여기서 주의할 점은 0의 개수 카운트를 next 진행 중에 진행해야 한다는 점입니다. 큐에 들어가지 못하지만 현재 상태가 이미 바이러스가 확산이 다 된 상태라면 그 값을 리턴해야 하기 때문입니다.

다음은 코드입니다.

import javax.annotation.processing.SupportedSourceVersion;
import java.util.*;
import java.io.*;

class Main{
    static int N,M;
    static int[][] map;
    static boolean[][] check;
    static boolean[] virusCheck;
    static List<Virus> virusList = new ArrayList<>();
    static int res = Integer.MAX_VALUE, zero = 0;
    static int[] dy = {1,0,-1,0}, dx = {0,1,0,-1};

    public static void main(String[] args) throws Exception{
        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];
        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 Virus(i,j,0));
                else if(map[i][j] == 0) zero++;
            }
        }
        virusCheck = new boolean[virusList.size()];

        if(zero == 0) System.out.println(0);
        else{
            backtracking(0,0);
            if(res == Integer.MAX_VALUE) System.out.println(-1);
            else System.out.println(res);
        }
    }

    static void backtracking(int idx, int cnt){
        if(cnt == M){
            bfs();
            return;
        }

        for(int i=idx;i<virusCheck.length;i++){
            if(!virusCheck[i]){
                virusCheck[i] = true;
                backtracking(i+1,cnt+1);
                virusCheck[i] = false;
            }
        }
    }

    static void bfs(){
        check = new boolean[N][N];
        Queue<Virus> queue = new ArrayDeque<>();
        for(int i=0;i<virusCheck.length;i++){
            if(virusCheck[i]){
                Virus v = virusList.get(i);
                queue.add(v);
                check[v.y][v.x] = true;
            }
        }

        int cnt = zero;
        while(!queue.isEmpty()){
            Virus curr = queue.poll();

            for(int i=0;i<4;i++){
                int ny = curr.y + dy[i];
                int nx = curr.x + dx[i];
                if(ny<0 || ny>=N || nx<0 || nx>=N) continue;
                if(check[ny][nx] || map[ny][nx]==1) continue;

                if(map[ny][nx]==0) cnt--;

                if(cnt == 0){
                    res = Math.min(res, curr.cnt+1);
                    return;
                }

                check[ny][nx] = true;
                queue.add(new Virus(ny,nx,curr.cnt+1));
            }
        }

    }

    static class Virus{
        int y;
        int x;
        int cnt;

        Virus(int y, int x, int cnt){
            this.y = y;
            this.x = x;
            this.cnt = cnt;
        }
    }
}