[BOJ] Q18405 경쟁적 전염

[BOJ] Q18352 경쟁적 전염

Question

Language: Python

Difficulty: Gold 5

각각의 바이러스는 1~k 까지의 번호를 지니며, 낮은 번호를 지닌 바이러스 부터 전이된다. 이미 바이러스가 있는 칸으로는 다른 바이러스가 침투하지 못한다.

낮은 번호를 가지는 바이러스부터 bfs를 진행하면 된다.

큐에 바이러스 종류, 바이러스의 좌표를 저장해 bfs를 수행한다.

Solution

from collections import deque
def bfs(n,graph,time_passed):
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    queue=[]
    for i in range(n):
        for j in range(n):
            if graph[i][j]!=0:
                queue.append((graph[i][j],0,i,j))
    queue.sort()
    queue=deque(queue)

    while queue:
        virus,current_time,y,x=queue.popleft()
        if current_time == time_passed:
            break
        for i in range(4):
            new_y=y+dy[i]
            new_x=x+dx[i]

            if new_y < 0 or new_y >=n or new_x < 0 or new_x >=n:
                continue
      
            if graph[new_y][new_x]==0:
                graph[new_y][new_x]=virus
                queue.append((virus,current_time+1,new_y,new_x))
        
n,k=map(int,input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))
time_passed,target_y,target_x=map(int,input().split())

bfs(n,graph,time_passed)

print(graph[target_y-1][target_x-1])