#18405번: 경쟁적 전염

문제

18405번: 경쟁적 전염

좌표계를 주고 바이러스의 전염을 확인하는데, 바이러스가 순번에 따라 전염되는 경우에 대한 문제이다. 인접한 시험관부터 한 칸씩 차례대로 전염되므로, BFS 알고리즘을 통해 해결할 수 있다.

풀이

특정 노드를 시작점으로 잡았던 다른 BFS 문제와 달리, 최초 바이러스가 있는 모든 노드를 처음 시작 queue에 넣어야 한다. 이 때, 바이러스의 종류에 따라 전염되는 순서가 다르므로 각 바이러스 종류에 따라 다른 queue를 만들어두었다. 이를 위해 최초 데이터 입력 후 바이러스가 어떤 노드에 있는지 확인이 필요한데, 시간 복잡도를 O(N^2) 안에서 처리하기 위해 이 때에도 BFS를 적용하였다.

import sys
from collections import deque
n, k = map(int, input().split())
examiner = []
for i in range(n):
    tmp = list(map(int, sys.stdin.readline().split()))
    examiner.append(tmp)
s, x, y = map(int, input().split())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

virus = [deque() for _ in range(k+1)]
visited = [[False for _ in range(n)] for _ in range(n)]
queue = deque([(0, 0)])
visited[0][0] = True
if examiner[0][0]!=0:
    virus[examiner[0][0]].append((0,0))
while queue:
    cur = queue.popleft()
    for i in range(4):
        tmpx = cur[0]+dx[i]
        tmpy = cur[1]+dy[i]
        if tmpx>=0 and tmpx<n and tmpy>=0 and tmpy<n and not visited[tmpx][tmpy]:
            queue.append((tmpx, tmpy))
            visited[tmpx][tmpy]=True
            if examiner[tmpx][tmpy]!=0:
                num = examiner[tmpx][tmpy]
                virus[num].append((tmpx, tmpy))             

def bfs(graph, num):
    l = len(virus[num])
    for _ in range(l):
        (x, y) = virus[num].popleft()
        for i in range(4):
            tmpx = x+dx[i]
            tmpy = y+dy[i]
            if tmpx>=0 and tmpx<n and tmpy>=0 and tmpy<n:
                if graph[tmpx][tmpy]>0:
                    continue
                elif graph[tmpx][tmpy]==0:
                    graph[tmpx][tmpy] = num
                    virus[num].append((tmpx, tmpy))

for _ in range(s):
    for i in range(k):
        bfs(examiner, i+1)

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

모든 바이러스를 그 번호에 따라 순차적으로 순서를 맞추어 한 큐 상에 넣는 방법도 존재한다. 한 큐 상에 넣을 경우, 무조건 s차례 반복한 나의 방식과 달리 s초가 되기 전에 큐가 비면 시행을 종료하는 방식으로 적용 가능하다.