경쟁적 전염 (bfs , 우선순위큐)

 

heapq를 통해 우선순위를 처리해주었고 s라는 시간을 처리하기 위해 큐 두개를 만들어 시간이 1초씩 지날때마다 한쪽을 비우고 다른 큐에 넣게를 반복해 s의 1초씩을 처리해주었습니다.

 

from collections import deque
import heapq

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

board = [[0]*n for _ in range(n)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]

for i in range(n):
    lines = list(map(int,input().split()))
    for j in range(n):
        board[i][j]= lines[j]

s, x, y = map(int, input().split())

def bfs(s):
    global board
    q1 = []
    q2 = []

    for i in range(n):
        for j in range(n):
            if board[i][j]!=0:
                heapq.heappush(q1,(board[i][j],i,j,1))

    while s>0:
        # print(q2)
        if not q2:
            while q1:
                front = heapq.heappop(q1)
                cv = front[0]
                cx = front[1]
                cy = front[2]
                ct = front[3]
                # print(cv,cx,cy)
                
                for i in range(4):
                    nx = cx+dx[i]
                    ny = cy+dy[i]
                    nv = cv
                    nt = ct+1
                    if nx>=0 and nx<n and ny>=0 and ny<n:
                        if board[nx][ny]==0:
                            heapq.heappush(q2,(nv,nx,ny,nt))
                            board[nx][ny]=nv
        else:
            while q2:
                front = heapq.heappop(q2)
                cv = front[0]
                cx = front[1]
                cy = front[2]
                ct = front[3]
                # print(cv,cx,cy)
                
                for i in range(4):
                    nx = cx+dx[i]
                    ny = cy+dy[i]
                    nv = cv
                    nt = ct+1
                    if nx>=0 and nx<n and ny>=0 and ny<n:
                        if board[nx][ny]==0:
                            heapq.heappush(q1,(nv,nx,ny,nt))
                            board[nx][ny]=nv
        s-=1
# print(s)
bfs(s)

# for i in range(n):
#     print(board[i])
# print()