백준24513 좀비 바이러스(파이썬)
백준24513 좀비 바이러스(파이썬)
https://www.acmicpc.net/problem/24513
문제
여기 NxM 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 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 : 바이러스에 감염된 마을
- 2 : 2번 바이러스에 감염된 마을
1번 바이러스와 2번 바이러스에 감염된 마을은 각각 하나씩만 주어진다
출력
1번, 2번, 3번 바이러스에 감염된 마을의 수를 공백으로 구분하여 한 줄에 출력한다
코드
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
maps = []
visited = [[0 for _ in range(M)] for _ in range(N)]
q = deque()
for i in range(N):
m = list(map(int, input().split()))
for j in range(M):
if m[j] == 1:
q.append((i, j , 1, 0))
elif m[j] == 2:
q.append((i, j, 2, 0))
maps.append(m)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while q:
x, y, v, d = q.popleft()
if maps[x][y] != 3:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < M:
if maps[nx][ny] == 0:
maps[nx][ny] = v
visited[nx][ny] = d+1
q.append((nx, ny, v, d+1))
elif maps[nx][ny] != -1 and maps[nx][ny] != v:
if visited[nx][ny] == d+1:
maps[nx][ny] = 3
v1, v2, v3 = 0, 0, 0
for i in range(N):
for j in range(M):
if maps[i][j] == 1: v1 += 1
elif maps[i][j] == 2: v2 += 1
elif maps[i][j] == 3: v3 += 1
print(v1, v2, v3)
