백준 24513번: 좀비바이러스(Python/Java)

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

24513번: 좀비 바이러스

 

 

 

접근

---

간단한 너비 우선 탐색에 조건이 몇 가지 추가된 문제다. 그래프를 탐색하며 1번 바이러스, 2번 바이러스가 접근한 곳인지 체크하는 것은 어렵지 않은 부분이라 대부분의 사람들이 쉽게 구현할 수 있었을 것이라 생각한다. 중요한 것은 1번 바이러스와 2번 바이러스가 만나 3번 바이러스가 되는 경우를 구현하는 것이다. 이 부분은 방문 확인하는 배열을 3차원 배열로 만들어주어 구현했다.

 

문제 조건을 확인해보자. '한 마을을 완전히 감염시키는 데 1시간 걸린다.', '마을이 완전히 감염되어야 다른 마을로 퍼져나갈 수 있으며 다른 바이러스가 완전히 감염시킨 마을은 침범하지 않는다.' 이 조건을 인지한 상태로 방문 확인 배열을 살펴보자. 배열을 3차원으로 만든 이유는 가로, 세로 인덱스를 체크한 뒤, 해당 위치에 방문한 바이러스와 방문한 시간을 기록하기 위함이다. 이제 이를 기준으로 해당 칸에 방문했는지, 그리고 방문했더라도 이 칸의 바이러스가 3번 바이러스가 되는지 확인하도록 한다.

 

예를 들어 생각해보자. 만일 [2, 2] 칸에 1번 바이러스가 출발한 지 4시간 후에 도착했다고 하자. 해당 칸은 아무것도 도착한 적이 없는 칸이다. 그렇다면 이 칸의 방문 배열은 [1, 4]가 된다. 이제 2번 바이러스가 다시 [2, 2] 칸에 출발한 지 4시간 후에 도착했다고 하자. 방문 배열을 확인했을 때 여기는 이미 1번 바이러스가 전염된 곳이다. 하지만 출발한 지 4시간 후에 도착했다. 즉, 아직 완벽하게 감염시키지 못했다. 그렇다면 이 칸은 3번 바이러스가 된다. 이때 해당 칸의 방문 배열을 3번 바이러스로 수정해주자.

 

그런데 만일 2번 바이러스가 4시간 뒤가 아니라 5시간 뒤에 도착했다고 생각해보자. 1번 바이러스는 4시간 후에 도착했고 5시간 후면 이미 한 시간이 지난 후다. 즉, 이미 해당 마을은 1번 바이러스에 완벽하게 감염되었다. 즉, 해당 칸은 2번 바이러스가 도착해도 별 다른 행동을 하지 못하고 넘어가야 한다.

 

이제 확인해야 하는 조건들이 정리가 된다. 우선 해당 칸을 감염시킨 바이러스가 있는지 확인(없다면 그냥 감염되었다 처리), 감염시킨 바이러스가 있다면 현재 접근한 바이러스와 기존 감염시킨 바이러스가 같은 바이러스인지 확인(같거나 3번 바이러스라면 그냥 넘어감), 서로 다른 바이러스일 시, 감염시킨 시간을 확인(현재 접근한 바이러스가 마을이 감염된 시간보다 적거나 같은 시간대라면 3번 바이러스로 변동처리, 아니라면 완벽하게 감염된 마을이기 때문에 그냥 넘어감). 이 조건들을 잘 구현한다면 문제를 해결할 수 있다.

 

한 가지 덧붙여, 마지막에 다시 한번 배열을 탐색하여 각 바이러스 별 숫자를 세면 연산이 NXM횟수만큼 늘어나기 때문에 이를 방지하기 위해 방문 탐방 시 바로바로 처리하도록 했다.

 

 

 

풀이

---

Python

from collections import deque

upDown = [-1, 1, 0, 0]
leftRight = [0, 0, -1, 1]

height, width = map(int, input().split())

board = [[0 for i in range(width)] for i in range(height)]
visitList = [[[0, 0] for i in range(width)] for i in range(height)]
bfsDeque = deque()

for i in range(height):
    firstLine = input().split()
    for j in range(width):
        board[i][j] = int(firstLine[j])

        if board[i][j] == 1:
            bfsDeque.append([i, j, 1, 0])
            visitList[i][j] = [1, -1]
        elif board[i][j] == 2:
            bfsDeque.append([i, j, 2, 0])
            visitList[i][j] = [2, -1]

result = [0, 1, 1, 0]
while bfsDeque:
    thisDeque = bfsDeque.popleft()

    if visitList[thisDeque[0]][thisDeque[1]][0] != 3:
        for i in range(4):
            thisHeight = (thisDeque[0] + upDown[i])
            thisWidth = (thisDeque[1] + leftRight[i])

            if 0 <= thisHeight < height and 0 <= thisWidth < width:
                if board[thisHeight][thisWidth] != -1:
                    if visitList[thisHeight][thisWidth][0] != 3:
                        if visitList[thisHeight][thisWidth][0] == 0:
                            visitList[thisHeight][thisWidth] = [thisDeque[2], (thisDeque[3]+1)]
                            result[thisDeque[2]] += 1
                            bfsDeque.append([thisHeight, thisWidth, thisDeque[2], (thisDeque[3]+1)])

                        else:
                            if thisDeque[2] != visitList[thisHeight][thisWidth][0]:
                                if (thisDeque[3]+1) <= visitList[thisHeight][thisWidth][1]:
                                    result[visitList[thisHeight][thisWidth][0]] -= 1
                                    result[3] += 1
                                    visitList[thisHeight][thisWidth] = [3, (thisDeque[3]+1)]

print(result[1], result[2], result[3])

 

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {

        int[] upDown = {-1, 1, 0, 0};
        int[] leftRight = {0, 0, -1, 1};

        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int height = Integer.parseInt(firstLine[0]), width = Integer.parseInt(firstLine[1]);

        int[][] board = new int[height][width];
        int[][][] visitList = new int[height][width][2];

        Queue<int[]> bfsQueue = new LinkedList<>();
        for(int i = 0 ; i < height ; i++){
            String[] secondLine = (scan.nextLine()).split(" ");
            for(int j = 0 ; j < width ; j++){
                board[i][j] = Integer.parseInt(secondLine[j]);

                if(board[i][j] == 1){
                    bfsQueue.add(new int[] {i, j, 1, 0});
                    visitList[i][j] = new int[] {1, -1};

                }else if(board[i][j] == 2){
                    bfsQueue.add(new int[] {i, j, 2, 0});
                    visitList[i][j] = new int[] {2, -1};
                }
            }
        }

        int[] result = {0, 1, 1, 0};
        while(!bfsQueue.isEmpty()){
            int[] thisQueue = bfsQueue.poll();

            if(visitList[thisQueue[0]][thisQueue[1]][0] != 3){
                for(int i = 0 ; i < 4 ; i++){
                    int thisHeight = (thisQueue[0] + upDown[i]);
                    int thisWidth = (thisQueue[1] + leftRight[i]);

                    if(thisHeight >= 0 && thisHeight < height && thisWidth >= 0 && thisWidth < width){
                        if(board[thisHeight][thisWidth] != -1){
                            if(visitList[thisHeight][thisWidth][0] != 3){
                                if(visitList[thisHeight][thisWidth][0] == 0){
                                    visitList[thisHeight][thisWidth] = new int[] {thisQueue[2], (thisQueue[3]+1)};
                                    result[thisQueue[2]]++;
                                    bfsQueue.add(new int[] {thisHeight, thisWidth, thisQueue[2],(thisQueue[3]+1)});
                                
                                }else{
                                    if(thisQueue[2] != visitList[thisHeight][thisWidth][0]){
                                        if((thisQueue[3]+1) <= visitList[thisHeight][thisWidth][1]){
                                            result[visitList[thisHeight][thisWidth][0]]--;
                                            result[3]++;
                                            visitList[thisHeight][thisWidth] = new int[] {3, thisQueue[3]+1};
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        System.out.println(result[1] + " " + result[2] + " " + result[3]);

    }

}