백준 경쟁적 전염 코드 및 해설 (파이썬)

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

18405번: 경쟁적 전염

 

시험관의 상태를 n초마다 업데이트하여 풀이했습니다. 각 바이러스의 위치는 딕셔너리로 저장했고, 딕셔너리의 value는 큐로 만들어 처리 완료된 경우 pop할 수 있도록 했습니다.

contaminate 함수를 통해 매 초마다 시험관을 업데이트 합니다. 1~K번 바이러스까지 차례대로 딕셔너리에 해당 바이러스 번호가 key로 있으면 해당 key의 모든 value들(좌표들)에 대해 다음을 시행합니다. 우선 한 번 처리되었으면 다시 처리될 필요가 없으므로 현재 처리하고 있는 좌표는 pop합니다. 이후 현재 위치의 상하좌우를 확인하고, 상하좌우 중에서 N*N 안에 있고, 0으로 비어있는 곳이 있으면 모두 현재 바이러스 번호로 감염시킵니다. 이후 새로 바이러스가 생겼으므로 이 위치를 next_virus라는 딕셔너리에 추가해줍니다. 

이를 S초까지 반복하고, 그때의 시험관 상태에서 (x,y) 좌표의 값을 프린트합니다.

 

import sys
from collections import defaultdict, deque

# N: 시험관의 크기
# K: 바이러스의 종류
N, K = map(int, sys.stdin.readline().split())

# 시험관
graph = []
# key: 바이러스 번호, value: 바이러스 좌표들의 리스트  
virus = defaultdict(deque)

for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    for j, v in enumerate(row):
        if v > 0:
            virus[v].append((i,j))
    graph.append(row)

# S초 후 (x,y) 좌표의 상태
S, x, y = map(int, sys.stdin.readline().split())
# 상하좌우
UDLR = [(-1,0), (1,0), (0,-1), (0,1)]

def contaminate(graph, virus, K):
    # 1초 후 바이러스들의 좌표 
    next_virus = defaultdict(deque)
    # 1~K 바이러스 차례대로 
    for v in range(1, K+1):
        if v in virus:
            while virus[v]:
                current = virus[v].popleft()
                # 현재 바이러스의 상하좌우 좌표 
                pos = []
                for udlr in UDLR:
                    pos.append(tuple([sum(x) for x in zip(current, udlr)]))
                for p in pos:
                    a,b = p
                    # N*N 안에 있고 현재 비어있으면 전염 
                    if a in range(0,N) and b in range(0,N) and graph[a][b] == 0:
                        graph[a][b] = v
                        next_virus[v].append((a,b))
    return graph, next_virus

# S초까지 반복 
second = 1
while second <= S:
    graph, virus = contaminate(graph, virus, K)
    second += 1

print(graph[x-1][y-1])