[DFS/BFS] (3) 경쟁적 전염

이코테 p.344 경쟁적 전염

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

18405번: 경쟁적 전염

해설 및 소스코드

• BFS를 이용하여 바이러스 증식 구현
• BFS 구현을 위해 큐를 이용
• 번호가 작은 바이러스부터 증식시켜야 하기 때문에 초기에 큐에 현재 존재하는 모든 바이러스 정보를 삽입한 후, 바이러스 번호 기준으로 오름차순 정렬
• 번호가 작은 바이러스부터 큐에서 꺼낸 후, 해당 바이러스의 상하좌우에 대해 확인하여 증식할 수 있는 경우 증식
• 큐가 빌 때까지, 혹은 시간이 다 될 때까지 반복

from collections import deque

# 입력 받기
n, k = map(int, input().split())
graph = [] # 맵 리스트
virus_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 좌표) 형태의 데이터 삽입
      virus_data.append((graph[i][j], 0, i, j))
virus_data.sort() # 바이러스 번호를 기준으로 오름차순 정렬
q = deque(virus_data) # 큐로 변환
target_s, target_x, target_y = map(int, input().split())

# 상, 하, 좌, 우 방향에 대한 정보 리스트
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 수행
while q:
  virus, s, x, y = q.popleft()
  if s == target_s: # 큐가 빌 때까지, 혹은 시간이 다 될 때까지 반복
    break
  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])