Java - [BOJ]17141 - 연구소 3

출처

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

 

문제

비활성화된 바이러스가 있는 연구실이 주어진다. 바이러스는 활성화 되면 상하좌우가 동시에 감염된다. 이 중 M개의 바이러스를 골라 활성화상태로 시킨다고 할때, 연구실에 빈곳 없이 모두 감염될때 까지 걸리는 최소 시간을 구하는 문제이다.

풀이

먼저, 우리는 비활성화인 바이러스 중 M개를 골라야 한다. M개의 순서는 상관이 없기 때문에 순열이 아닌 조합을 구해야하며, 자바에서 조합을 구하기 위해서는 DFS를 활용해야 한다.

 

먼저, 바이러스의 위치가 담긴 List<Node>를 만들고 이 중 M개만 조합을 만든 뒤 바이러스를 전염시켜야 한다. M개의 조합을 기록하기 위해 DFS에서 현재 고른 배열을 들고다닐수도 있지만, 메모리 절약을 위해 전역 변수로 Node[] 배열을 만들어 기록하도록 하였다.

 

또한 문제 조건을 잘 읽어보면, 모든 칸을 남김없이 바이러스에 감염시켜야 하지만 비활성화된 바이러스도 바이러스에 감염된 것으로 친다. 만약 6초동안 1칸만을 제외하고 모두 감염이 되었는데 마지막 남은 한 칸이 비활성화된 바이러스라면, 굳이 1초를 더 소요해 건드려서 활성화 시킬 필요 없이 6초에서 마무리 하면 된다는 뜻이다.

 

따라서 빈칸의 갯수를 초기에 카운트 해놓고, BFS를 진행하며 감염시킨 빈칸 갯수를 센 뒤 비교하여 모두 채워졌는지 판단한다. 또한 비활성화된 바이러스 까지 BFS에서 방문은 하지만(비활성화 된 바이러스를 지나가도 됨), 초는 세지 않기 위해 비활성화된 바이러스가 존재하는 칸은 0으로 초기화 한다.

 

자세한 풀이는 아래 코드를 참조

 

코드

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

public class Main {
    static int[][] map;
    static int N, M, answer, zeroCnt;
    static List<Node> virus;
    static Node[] nowSelect;
    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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

        virus = new ArrayList<>();
        nowSelect = new Node[M];


        map = new int[N][N];
        answer = Integer.MAX_VALUE;
        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] == 1) map[i][j] = -1;
                else if (map[i][j] == 2) {
                    map[i][j] = -2;
                    virus.add(new Node(i, j));
                }
                else zeroCnt++;
            }
        }

        dfs(0, 0);
        
        answer = answer == Integer.MAX_VALUE ? -1 : answer;
        bw.write(answer + "\n");
        br.close();
        bw.flush();
        bw.close();
    }

    static void dfs(int start, int cnt) {
        if (cnt == M) {
            answer = Math.min(afterVirus(), answer);
            return;
        }

        for(int i = start; i < virus.size(); i++) {
            nowSelect[cnt] = virus.get(i);
            dfs(i + 1, cnt + 1);
        }

    }

    public static int[][] copyArr() {
        int[][] tmp = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j =0 ; j < N; j++) {
                tmp[i][j] = map[i][j];
            }
        }
		return tmp;
    }

    static int afterVirus() {
        Deque<Node> q = new ArrayDeque<>();
        int[][] tmp = copyArr();
        boolean[][] visited = new boolean[N][N];

        for (Node x : nowSelect) {
            if (tmp[x.x][x.y] == -2) {
                q.addFirst(x);
                visited[x.x][x.y] = true;
                tmp[x.x][x.y] = 0;
            }
        }
        
        
        int nowCnt = 0;
        while (!q.isEmpty()) {
            Node now = q.pollLast();

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (isRange(nx, ny) && tmp[nx][ny] != -1 && !visited[nx][ny]) {
                    if (map[nx][ny] == 0) {
                        nowCnt++;
                    }
                    q.addFirst(new Node(nx, ny));
                    visited[nx][ny] = true;
                    tmp[nx][ny] = tmp[now.x][now.y] + 1;
                }
            }

        }

        if (zeroCnt != nowCnt) {
            return Integer.MAX_VALUE;
        }
        return check(tmp);
    }

    public static int check(int[][] tmp) {
        int now_max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == -2) tmp[i][j] = 0;
                now_max = Math.max(now_max, tmp[i][j]);
            }
        }
        
        return now_max;
    }

    static boolean isRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }

     static class Node {
        int x;
        int y;

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

}