[백준 Gold 4] 17142 연구소 3 - Java

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

17142번: 연구소 3

 

접근 과정 : 

• 연구소의 빈칸에 모두 바이러스가 있게 만드는 시간을 구하는 문제이다.
• 활성화 여부에 상관없이, 모든 칸에 바이러스가 있으면 된다..
• 활성화 바이러스를 선택하는 조합을 구성하고, 각 조합에 따라 BFS로 바이러스가 퍼지는 시뮬레이션을 실시한다.
• BFS에서는 미리 체크한 빈칸의 갯수(벽과 바이러스를 제외한)를 확인하면서 빈칸이 0이 되었을 때 리턴한다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    연구소 3
*/

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

public class BOJ17142 {

    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());
        S = 0;
        lab = new int[N][N];
        virus = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                lab[i][j] = Integer.parseInt(st.nextToken());
                if (lab[i][j] == 2) {
                    virus.add(new int[] { i, j });
                } else if (lab[i][j] == 0) {
                    S++;
                }
            }
        }

        if (S == 0) {
            System.out.println(0);
        } else {
            active = new int[M];
            T = -1;
            choiceVirus(0, 0);

            System.out.println(T);
        }

    }

    static int N, M, T, S;
    static int[][] lab;
    static List<int[]> virus;
    static int[] active;
    static int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    static void choiceVirus(int index, int depth) {
        if (depth == M) {
            // 시뮬레이션

            simulation();

            return;
        }

        if (index == virus.size()) {
            return;
        }

        active[depth] = index;
        choiceVirus(index + 1, depth + 1);
        choiceVirus(index + 1, depth);
    }

    static void simulation() {

        boolean[][] visit = new boolean[N][N];

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
            return a[2] - b[2];
        });

        for (int i = 0; i < M; i++) {

            int[] v = virus.get(active[i]);
            visit[v[0]][v[1]] = true;
            queue.add(new int[] { v[0], v[1], 0 });
        }

        int space = S;

        while (!queue.isEmpty()) {

            int[] v = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = v[0] + move[i][0];
                int ny = v[1] + move[i][1];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
                    continue;
                }
                if (lab[nx][ny] == 1 || visit[nx][ny]) {
                    continue;
                }

                if (lab[nx][ny] == 0) {
                    space--;
                }
                if (space == 0) {
                    if (T == -1) {
                        T = v[2] + 1;
                    } else {
                        T = Math.min(T, v[2] + 1);
                    }
                    return;
                }

                visit[nx][ny] = true;
                queue.add(new int[] { nx, ny, v[2] + 1 });

            }
        }
    }

}

 

P.S 

시작부터 완전 꼬여서 고생했다.

코테였으면 망했거나, 코드를 싹 지우고 다시 시작했을 것이다.

지금 풀이코드도 상당히 더러운데.. 좀 짜증나서 지금은 꼴도 보기 싫다.