[좀비 바이러스/G3/Python3]

24513번 좀비 바이러스 G3

 

문제
여기 N x M 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가 버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 1번, 2번, 3번으로 번호를 매겼다. 바이러스의 특징은 다음과 같다. 1번과 2번 바이러스는 치사율은 낮지만 전염성이 강해 상하좌우에 인접해 있는 마을로 동시에 퍼져나가며 한 마을을 완전히 감염시키는 데 1시간 걸린다.마을이 완전히 감염되어야 다른 마을로 퍼져나갈 수 있으며 다른 바이러스가 완전히 감염시킨 마을은 침범하지 않는다. 마을이 한 바이러스에 완전히 감염되기 전에 다른 종류의 바이러스가 마을에 도착하면 3번 바이러스가 만들어진다. 3번 바이러스는 치사율이 높은 만큼 전염성이 약해 감염된 마을에서 더 이상 퍼지지 않는다. 치료제를 갖고 있는 마을은 감염시킬 수 없다. 1번 바이러스와 2번 바이러스에 감염된 마을이 나와버렸다. 바이러스가 퍼질 수 있는 대로 퍼졌을 때 1번, 2번, 3번 바이러스에 감염된 마을이 각각 몇 개일지 구해보자.

입력
첫째 줄에 N(2≤N≤1000)과 M(2≤M≤1000)이 주어진다.
둘째 줄부터 N개의 줄에 걸쳐 마을의 상태가 M개 주어진다. 마을의 상태는 다음과 같이 이루어져 있다.
 −1: 치료제를 가진 마을,  0: 아직 감염되지 않은 마을,  1: 1번 바이러스에 감염된 마을,   2: 2번 바이러스에 감염된 마을
1번 바이러스와 2번 바이러스에 감염된 마을은 각각 하나씩만 주어진다.

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

그래프 이론, 그래프 탐색, 너비 우선 탐색

 

일반적인 BFS로 감염시키는 문제와 달리 완전 감염이라는 개념이 포함되어 있다.

이 때문에 탐색 이전에 완전히 감염된 집의 경우 완전 감염 처리를 진행해야한다.

 

모든 탐색이 완료되면, 모든 마을을 확인하여 개수를 구한다.

 

import sys
from collections import deque

col, row = map(int, sys.stdin.readline().split())

maze = [list(map(int, sys.stdin.readline().split())) for _ in range(col)]
can_change = [[True] * row for _ in range(col)]
varius = deque()

for i in range(col):
    for j in range(row):
        if maze[i][j] <= 0: continue
        varius.append((i, j))
        can_change[i][j] = False

move = [[-1,0],[1,0],[0,1],[0,-1]]


va_cnt = [0, 0, 0]

while varius:
    for y, x in varius:
        can_change[y][x] = False
    for _ in range(len(varius)):
        y, x = varius.popleft()
        if maze[y][x] == 3: continue
        for ay, ax in move:
            dy, dx = y+ay, x+ax
            if dy<0 or dx<0 or dy>=col or dx>=row: continue
            if maze[dy][dx] == -1: continue
    
            if maze[dy][dx] == 0:
                varius.append((dy, dx))
                maze[dy][dx] = maze[y][x]
                continue
            
            if maze[dy][dx] + maze[y][x] == 3 and can_change[dy][dx]:
                maze[dy][dx] = 3
                continue

for i in range(col):
    for j in range(row):
        if maze[i][j] <= 0: continue
        va_cnt[maze[i][j]-1] += 1

print(*va_cnt)​

 

---