[JAVA] 백준 17141번 : 연구소 2

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

17141번: 연구소 2

---

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

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int minTime = Integer.MAX_VALUE, empty;
    static List<Pos> existVirus = new ArrayList<>();
    static Stack<Pos> selectedVirus = new Stack<>();
    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) //바이러스 위치 리스트에 추가
                    existVirus.add(new Pos(i, j, 0));
                else if(map[i][j] == 0)
                    empty++;
            }
        }
        
        empty += existVirus.size();
        //선택되지 않은 바이러스 자리는 빈칸 취급 하므로 바이러스 개수까지 포함해서 카운팅 해 줘야 함!

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

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

    private static void selectVirus(int start, int cnt) {
        if (cnt == M) { //모두 선택한 경우 시뮬레이션 시작
            spreadVirus();
            return;
        }
        if(start >= existVirus.size())
            return;
        for (int i = start; i < existVirus.size(); i++) {
            selectedVirus.push(existVirus.get(i));
            selectVirus(i + 1, cnt + 1);
            //System.out.printf("i : %d, cnt = %d", i, cnt);
            selectedVirus.pop();
        }
    }

    private static void spreadVirus() {
        //bfs + selectVirusSET 활용해 시뮬레이션
        Queue<Pos> queue = new LinkedList<>(selectedVirus);
        Stack<Pos> tmp = new Stack<>();
        tmp.addAll(selectedVirus);
        visited = new boolean[N][N];
        int cnt = selectedVirus.size();
        int maxTime = 0;
        while (!tmp.isEmpty()) {
            Pos pos = tmp.pop();
            visited[pos.x][pos.y] = true;
            queue.add(pos);
        }

        while (!queue.isEmpty()) {
            Pos now = queue.poll();
            maxTime = Math.max(maxTime, now.time);

            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 || visited[nx][ny] || map[nx][ny] == 1)
                    continue;
                visited[nx][ny] = true;
                cnt++;
                queue.add(new Pos(nx, ny, now.time + 1));
            }
        }
        //빈칸 모두 채웠을 경우에만 시간 갱신
        minTime = empty == cnt ? Math.min(minTime, maxTime) : minTime;
    }


    private static class Pos {
        int x;
        int y;
        int time;

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

💡 백트레킹, BFS

풀이

💡 특정 조합을 고려하는 경우, 재귀를 사용해 풀 것!

• 바이러스 M개를 선택하는 조합을 먼저 구한 뒤, 뽑아놓은 바이러스들을 기준으로 BFS 실행
  • 이때 조합은 재귀를 사용해 구한다.
  • 추가, 제거가 용이하도록 Stack 자료 구조를 사용했다.
  • 재귀 함수에서 M개를 만족했을 경우, 바로 바이러스 확산 시작(BFS)
  • https://www.acmicpc.net/problem/14502  >>> 바이러스 확산은 이 "연구소1" 경우와 동일
    • 사실 바이러스 M개 선택이나 벽 3개 세우는거나 재귀를 사용하는 전체적인 흐름은 동일하다.
• 바이러스 확산이 끝나고 난 뒤, map을 전부 돌며 체크해도 되지만, 채운 빈칸 개수를 비교해서 다 채웠는지 확인 과정을 거쳤다
  • map에 존재하는 빈칸 개수 empty와, 선택된 바이러스 조합이 채운 빈칸 개수 cnt
  • 해당 경우의 최대 시간도 마찬가지로 while문 안에서 비교해주며 처리함
  • empty == cnt 인 경우에만 minTime을 갱신해 줌
• 근데 굳이... maxTime값을 일일히 갱신하는 것 보다 time 배열 따로 사용해서 기록하고 나중에 time한번 돌아서 체크하는게 더 효율적일 것 같음
  • 대신 바이러스 있는 칸은 최대 시간에 카운팅 안하므로 if(map[i][j] == 0) 을 조건으로 내야 할 듯