[python] 백준18405_경쟁적 전염 (DFS&BFS)

문제

 

풀이

BFS를 이용하여 풀 수 있고, 각 바이러스가 낮은 번호부터 증식하기 때문에 초기에 큐에 원소를 삽입할 때 낮은 바이러스의 번호부터 삽입해야 한다.

큐에서 낮은 바이러스 번호부터 pop하여 상하좌우로 바이러스 번식시키고, 번식된 위치를 다시 큐에 넣고, 원하는 시간이 될 때까지 반복한다.

코드

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()) # 시간, 위치 x,y

# 바이러스가 퍼져나갈 수 있는 4가지 위치
dx = [-1,0,1,0]
dy = [0,1,0,-1]

# 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 nx>=0 and nx<n and ny>=0 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])