24513 좀비 바이러스

좀비 바이러스

문제

여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$번, $2$번, $3$번으로 번호를 매겼다.

바이러스의 특징은 다음과 같다.

 $1$번과 $2$번 바이러스는 치사율은 낮지만 전염성이 강해 상하좌우에 인접해 있는 마을로 동시에 퍼져나가며 한 마을을 완전히 감염시키는 데 1시간 걸린다.
마을이 완전히 감염되어야 다른 마을로 퍼져나갈 수 있으며 다른 바이러스가 완전히 감염시킨 마을은 침범하지 않는다.
마을이 한 바이러스에 완전히 감염되기 전에 다른 종류의 바이러스가 마을에 도착하면 $3$번 바이러스가 만들어진다.
 $3$번 바이러스는 치사율이 높은 만큼 전염성이 약해 감염된 마을에서 더 이상 퍼지지 않는다.
치료제를 갖고 있는 마을은 감염시킬 수 없다.

 $1$번 바이러스와 $2$번 바이러스에 감염된 마을이 나와버렸다. 바이러스가 퍼질 수 있는 대로 퍼졌을 때 $1$번, $2$번, $3$번 바이러스에 감염된 마을이 각각 몇 개일지 구해보자.

입력

첫째 줄에 $N$($2≤N≤1,000$)과 $M$($2≤M≤1,000$)이 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 마을의 상태가 $M$개 주어진다. 마을의 상태는 다음과 같이 이루어져 있다.

 $-1$: 치료제를 가진 마을
 $0$: 아직 감염되지 않은 마을
 $1$: $1$번 바이러스에 감염된 마을
 $2$: $2$번 바이러스에 감염된 마을
 $1$번 바이러스와 $2$번 바이러스에 감염된 마을은 각각 하나씩만 주어진다.

출력

 $1$번, $2$번, $3$번 바이러스에 감염된 마을의 수를 공백으로 구분하여 한 줄에 출력한다.

풀이

1번 바이러스와 2번 바이러스를 동시에 돌려야 한다. 즉 하나의 큐로 동작시킨다.
또한 시간을 확인하기 위해 우선순위큐를 이용해서 감염된 시간에 따라 순차적으로 상하좌우 감염을 진행한다.
0이 나오면 해당 바이러스로 감염시키고 1 혹은 2를 마주쳤을때 감염시키는 마을과 다른 바이러스라면 감염된 시간을 비교해서
같으면 3으로 변경시킨다.

핵심 아이디어는 큐에 위치 정보를 넣어 큐에서 뺏을 당시 1,2면 상하좌우로 감염을 진행하고 3이면 진행하지 않는 것이다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{

    static class Node implements Comparable<Node>{
        int x,y;
        int day;

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

        @Override
        public int compareTo(Node o){
            return day - o.day;
        }

        public String toString(){
            return x + " " + y + " " + day;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] graph = new int[n][m];
        int[][] days = new int[n][m];
        Queue<Node> queue = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] > 0)
                    queue.add(new Node(i, j, 0));
            }
        }


        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int x = node.x;
            int y = node.y;

            if(graph[x][y] == 3)
                continue;

            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if (graph[nx][ny] == 0) {
                    graph[nx][ny] = graph[x][y];
                    days[nx][ny] = days[x][y] + 1;
                    queue.add(new Node(nx, ny, days[nx][ny]));
                }

                if (graph[nx][ny] == 1 && graph[x][y] != 1) {
                    if (days[nx][ny] == days[x][y] + 1)
                        graph[nx][ny] = 3;
                }

                if (graph[nx][ny] == 2 && graph[x][y] != 2) {
                    if (days[nx][ny] == days[x][y] + 1)
                        graph[nx][ny] = 3;
                }
            }
        }

        int[] answer = new int[3];
        for(int[] arr : graph){
            for(int i : arr){
                if(i == 1)
                    answer[0]++;
                if(i==2)
                    answer[1]++;
                if(i==3)
                    answer[2]++;
            }
        }

        for(int i : answer)
            System.out.print(i + " ");
    }
}