쟁적 전염 백준 18405번 BFS

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

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

지난번 연구소랑 같으면서도 다른점이 있습니다.

바이러스간 순서가 있는데 결국 일반적인 DFS/BFS 문제에서 추가적으로 바이러스를 어떻게 관리하고 추적할건지 들어가면 될듯합니다.

from collections import deque

n,k = map(int, input().split())

graph = [] #전체 보드 정보를 담는 리스트
data = [] #바이러스에 대한 정보를 담는 리스트

for i in range(n):
    #보드 정보를 한 줄 단위로 입력
    graph.append(list(map(int,input().split())))
    for j in range(n):
        #해당 위치에 바이러스가 존재하는 경우
        if graph[i][j] != 0:
            #(바이러스 종류, 시간, 위치X,Y 삽입)
            data.append((graph[i][j], 0, i, j))

#정렬 이후에 큐로 옮기기(낮은 번호의 바이러스가 먼저 증식하므로)
data.sort()
q = deque(data)
target_s,target_x,target_y = map(int, input().split())
    
#4가지 이동 방향에 대한 리스트
dx = [-1,0,1,0]
dy = [0,1,0,-1]

바이러스를 관리하기 위해서 큐를 사용합니다. 그래서 내장된 deque 자료구조를 가져옵시다.

입력을 받을때는 바이러스의 종류와 위치 그리고 시간을 삽입해서 타겟을 관리를 해줍시다.

#너비 우선 탐색(BFS)진행
while q:
    virus, s, x, y = q.popleft()
    #정확히 s초가 지나거나, 큐가 빌때까지 반복
    if s == target_s:
        break
    #현재 노드에서 주변 4가지 위치를 각각 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        #상,하,좌,우 중에서 바이러스가 퍼질 수 있는 경우
        if 0 <= nx and nx <n and 0 <= ny and ny < n:
            #방문이 가능한데 아직 방문한적이 없다면 바이러스를 넣기
            if graph[nx][ny] == 0:
                graph[nx][ny] = virus
                q.append((virus,s+1,nx,ny))
    
print(graph[target_x-1][target_y-1])

이전과 비슷한 너비우선 탐색으로 진행이 됩니다.

q에서 바이러스를 관리한다고 했는데 여기서 첫번째 바이러스 예시에서는 1이었는데 시작을 합시다.

종료하는 조건은 s초가 지나거나 q에서 더 이상 뺄수 있는게 없을때까지 진행을 하게 됩니다.

각 바이러스는 4가지 위치를 동시에 확인을 하게 되는데 끝까지 가는게 아니라 일단 4방향으로만 가고 멈추게 됩니다. 그러니 재귀를 통해서 반복할 필요는 없이 한 바이러스당 4방향만 확인을 하면 끝이 납니다.

그리고 바이러스가 방문하지 않은 곳이라면(0이라면) 해당 바이러스 종류에 맞게 추가를 하고 q에다가 저장을 합시다.

해당 반복이 끝나면 조건에 맞는 바이러스를 출력하면 됩니다.