18405-경쟁적전염

www.acmicpc.net/problem/18405

1. Queue 를 이용해 먼저 전염된 순으로 전염을 진행함

2. 전염은 상하좌우로 한번씩만 진행됨

3. 바이러스 번호 순으로 전염을 해야하기 때문에 초기 바이러스를 정렬해줌

4. 초기의 노드들에 동일하게 0 이라는 시간값을 부여함. 이는 초기 노드들로부터 전염된 모든 노드들에게 0 + 1 이라는 시간값을 부여하기 위함.

5. Queue 가 빌 때까지 진행한 후, 해당 위치의 시간을 출력

from collections import deque

n,k = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
S, X, Y = map(int,input().split())

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

# 초기의 바이러스 위치 정보들
virus_info = []
for i in range(n):
    for j in range(n):
        if arr[i][j]:
            virus_info.append((arr[i][j],0,i,j))

# 바이러스 종류 순으로 정렬
virus_info.sort()
q = deque(virus_info)

# 큐가 빌 때까지 bfs 수행
while q:
    # 최우선 노드 꺼냄
    virus, time, y, x = q.popleft()
    # 원하는 위치에 도달했다면 break
    if time == S:
        break
    # 최우선 노드의 상하좌우 수행
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            if not arr[ny][nx]:
                # 인덱스 범위 안에 있고, 수행 안되어 있다면
                arr[ny][nx] = virus
                # !!! 기존 노드로부터 시간이 1 증가한 시간정보
                q.append((virus,time+1,ny,nx))

print(arr[X-1][Y-1])