[백준] 경쟁적 전염 18405번 (python)

출처 : 18405번: 경쟁적 전염 (acmicpc.net)

18405번: 경쟁적 전염

해결 방법

BFS 문제이다.

처음에는 번호가 작은 바이러스의 종류부터 증식을 시키기 위해 BFS의 매 초마다 우선순위 큐를 사용하여 

board를 탐색하여 추가해주었는데 이런 식으로 작성하니 시간 초과가 난다

생각해 보면 맨 처음에만 번호가 작은 바이러스의 종류 순으로 queue에 넣은 후 BFS함수를 돌며 

추가해 주어도 자동으로 번호가 낮은 순서대로 계속 추가된다는 것을 알았다.

bfs를 돌며 time 이 s와 같아지면 break 하면 완성된다.

from collections import deque
lab = []
dir = [[-1, 0],[0, -1],[1, 0],[0, 1]]
def makeQue():
    que = []
    for i in range(N):
        for k in range(N):
            if lab[i][k] != 0:
                que.append([lab[i][k], i, k, 0])
    que.sort()
    que = deque(que)
    return que
def BFS():
    while que:
        virus, x, y, time = que.popleft()
        if time == S:
            break
        for i in range(4):
            nextX = x + dir[i][0]
            nextY = y + dir[i][1]
            if (nextX >= 0 and nextY >= 0 and nextX < N and nextY < N):
                if (lab[nextX][nextY] == 0):
                    lab[nextX][nextY] = virus
                    que.append([virus, nextX,nextY,time + 1])


N, K = map(int, input().split())
for i in range(N):
    lab.append(list(map(int, input().split())))
S, X, Y = map(int, input().split())
que = makeQue()
BFS()
print(lab[X-1][Y-1])