[JAVA] 백준 17142번 : 연구소 3

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M, minTime = Integer.MAX_VALUE;
    static int[][] map, time;
    static boolean[][] visited;
    static List<Pos> virus = new ArrayList<>();
    static Stack<Pos> selectedVirus;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    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)
                    virus.add(new Pos(i, j));
            }
        }

        for (int i = 0; i < virus.size(); i++) {
            selectedVirus = new Stack<>();
            selectedVirus.push(virus.get(i));
            selectPos(i + 1, 1);
        }

        System.out.println(minTime == Integer.MAX_VALUE ? -1 : minTime);
    }

    private static void selectPos(int start, int cnt) {
        if(cnt == M){
            spreadVirus();
            return;
        }
        if(start >= virus.size())
            return;

        for (int i = start; i < virus.size(); i++) {
            selectedVirus.push(virus.get(i));
            selectPos(i + 1, cnt + 1);
            selectedVirus.pop();
        }
    }

    private static void spreadVirus() {
        Queue<Pos> queue = new LinkedList<>();
        Stack<Pos> stack = new Stack<>();
        stack.addAll(selectedVirus);
        time = new int[N][N];
        visited = new boolean[N][N];
        int maxTime = 0;
        boolean noEmpty = true;

        while (!stack.isEmpty()){
            Pos tmp = stack.pop();
            visited[tmp.x][tmp.y] = true;
            queue.add(tmp);
        }

        while (!queue.isEmpty()) {
            Pos now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] == 1 || visited[nx][ny])
                    continue;
                
                visited[nx][ny] = true;
                time[nx][ny] = time[now.x][now.y] + 1;
                queue.add(new Pos(nx, ny));
            }
        }

        outerloop:
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j] == 0){
                     if(!visited[i][j]) { //빈칸인데 방문하지 않음 -> -1
                         noEmpty = false;
                         break outerloop;
                     } else if(time[i][j] > maxTime)  //빈칸일 경우 최대 시간 갱신
                         maxTime = time[i][j];
                     
                }
            }
        }
        minTime = noEmpty ? Math.min(maxTime, minTime) : minTime;
    }

    private static class Pos {
        int x, y;

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

💡 백트레킹, BFS

풀이

유사 문제 : https://www.acmicpc.net/problem/17141 참고

17141번: 연구소 2

차이점

• 비활성화 된 바이러스를 만나면 활성화 시킨다 
  
  • 기존에는 비활성화 된 바이러스는 빈칸과 동일한 취급을 했었음 -> 빈칸을 모두 채우는 시간 == 비활성화 된 바이러스가 있는 칸 까지도 모두 닿아야 함
  • But 이번 문제는비활성화 바이러스는 활성 바이러스를 만났을 때 활성화 되고, 빈칸에 포함되지 않음
  • 즉, 활성 바이러스를 제외한 모든 칸이 비활성 바이러스인 경우, 기존에는 나머지 칸을 모두 채웠어야 했지만 이번 문제에서는 채우지 않고 바로 채웠다고 판단한다는 것 (= 0초)

---

• 소요 시간을 기록할 time배열, 지도 정보 담을 map 배열 각각 분리해서 선언, 초기 시작 바이러스를 위해 visited 배열을 생성해 체크
• M개의 바이러스를 선택하는 것은 전과 마찬가지로 재귀를 사용해 선정하고, M개를 채우면 BFS를 활용해 spread 메서드를 실행해 채움
• stack에 있는 pos를 queue에 넣을 때, EmptyStack Error 주의 (기존에 존재하는 selected에서 바로 꺼냈더니 당연 오류남..)
  • stack에 복사한 뒤 옮김
• 마지막에 최대 시간과, 안채워진 칸을 판별할 때 비활성 바이러스 고려를 잘 해줘야 한다.
  • 안채워진 칸 >> map 상에서 빈칸이어야 함  && 기록된 시간이 0이어야 함
  • 최대 시간 >> map 상에서 2가 아님 && 기록된 시간 중 최대값
  • => 둘 다 map[][] == 0 인 경우에 고려해야 함