[BaekJoon] 24513 좀비 바이러스 (Gold 3) - Python

문제

 

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

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

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

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

---

입출력 예시

 

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

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

•  −1$-1$: 치료제를 가진 마을
•  0$0$: 아직 감염되지 않은 마을
•  1$1$: 1$1$번 바이러스에 감염된 마을
•  2$2$: 2$2$번 바이러스에 감염된 마을

 1$1$번 바이러스와 2$2$번 바이러스에 감염된 마을은 각각 하나씩만 주어진다.

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

 

입력예시1)

4 4
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 2

출력예시1)

10 3 3

 

입력예시2)

7 9
0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 -1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 -1 0 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 -1 0 0
0 0 0 0 0 0 0 0 0

출력예시2)

25 29 6

---

코드

 

from collections import deque
import sys
input = sys.stdin.readline
INF = sys.maxsize

N, M = map(int, input().rstrip().split()) # 도시 크기 입력
grid = [] # 도시 입력 위한 리스트 생성
zombie_1 = None # 좀비1 시작 좌표
zombie_2 = None # 좀비2 시작 좌표
d = [(0, 1), (0, -1), (1, 0), (-1, 0)] # x, y 변화량

for i in range(N): # 도시 입력
    grid.append(list(map(int, input().rstrip().split())))
    for j in range(M):
        if grid[i][j] == 1: zombie_1 = (i, j) # 좀비1 시작 좌표 저장
        elif grid[i][j] == 2: zombie_2 = (i, j) # 좀비2 시작 좌표 저장


def bfs(): # BFS함수
    visit = [[0 for _ in range(M)] for _ in range(N)] # 거리 리스트 생성
    q = deque([])
    visit[zombie_1[0]][zombie_1[1]] = 1 # 좀비1은 양수
    visit[zombie_2[0]][zombie_2[1]] = -1 # 좀비2는 음수로 설정
    q.append((zombie_1[0], zombie_1[1], 1, 1)) # q에 x, y, 좀비종류, dist 추가
    q.append((zombie_2[0], zombie_2[1], 2, -1)) # q에 x, y, 좀비종류, dist 추가
    z1_cnt = 1 # 좀비1 카운트
    z2_cnt = 1 # 좀비2 카운트
    z3_cnt = 0 # 좀비3 카운트
    while q:
        x, y, z, dist = q.popleft() # x, y, 좀비종류, dist 뽑아오기
        if visit[x][y] == INF: continue # 거리가 INF면 그냥 continue
        for dx, dy in d: # 4방향 검사
            nx, ny = x + dx, y + dy
            if possible(nx, ny, visit): # 이동할 수 있는 곳이라면
                if visit[nx][ny] == 0: # 그리고 그곳이 방문한 적 없는 곳 이라면
                    if z == 1: # 방문한 적 없는 곳 이면서 좀비의 종류가 1이라면
                        visit[nx][ny] = dist + 1 # 해당 인덱스의 거리를 1 증가
                        z1_cnt += 1 # 좀비1 카운트 1 증가
                        q.append((nx, ny, 1, dist + 1)) # q에 추가
                    elif z == 2: # 좀비의 종류가 2라면
                        visit[nx][ny] = dist - 1 # 해당 인덱스의 거리를 -1 증가
                        z2_cnt += 1 # 좀비2 카운트 1증가
                        q.append((nx, ny, 2, dist - 1)) # q에 추가
                elif abs(visit[nx][ny]) == abs(dist) + 1 and ((visit[nx][ny] > 0 and z == 2) or (visit[nx][ny] < 0 and z == 1)): # 만약 동시에 도달했다면?
                    z3_cnt += 1 # 좀비3 카운트 1 증가
                    z1_cnt -= 1 # 좀비1 카운트 1 감소
                    # 여기에서 좀비1 카운트를 1 감소시킬 수 있는 이유?
                    # q에 좀비1을 먼저 원소로 대입했고, 이후에 좀비2를 대입했기 때문에
                    # q에서 뽑아오는 원소 순서상 좀비1이 움직인 이후에 좀비2가 움직인다.
                    # 따라서 좀비1 카운트를 감소시킬 수 있다.
                    visit[nx][ny] = INF # 해당 인덱스를 좀비3으로 표시하기 위해 INF로 교체
    return z1_cnt, z2_cnt, z3_cnt # 좀비 수 리턴

            
def possible(x, y, visit): # 방문 가능한지 판별하는 함수
    if x < 0 or y < 0 or x >= N or y >= M: return False # 도시 크기 범위를 벗어나면 False
    elif visit[x][y] == INF: return False # 좀비3 위치면 False
    elif grid[x][y] == -1: return False # 치료제 위치면 False
    return True # 아무것도 해당되지 않는다면 True

print(*bfs()) # 결과 출력

---

실행 화면

 

---

채점 결과