백준 알고리즘 18405번 경쟁적 전염(python)

생각보다 어려운 BFS 문제이다. 바이러스가 퍼지는 순서(작은 숫자부터)에 맞게

def bfs(x, y):
    check[x][y] = 1
    for dx, dy in d:
        X, Y = x+dx, y+dy
        if (0 <= X < N) and (0 <= Y < N) and graph[X][Y] == 0:
            check[X][Y] = 1
            graph[X][Y] = graph[x][y]

N, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
S, X, Y = map(int, input().split())
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
check = [[0]*N for _ in range(N)]
while S:
    li = []
    for i in range(N):
        for j in range(N):
            if graph[i][j] > 0:
                li.append([i, j])
    li.sort(key=lambda x:graph[x[0]][x[1]])
    for i, j in li:
        bfs(i, j)
    if graph[X-1][Y-1]:
        break
    S -= 1
print(graph[X-1][Y-1])