18405번 경쟁적 전염(python3)

https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

이번 문제는 bfs를 적용해서 풀 수 있었다.

처음 queue를 생성하고 최초 시험관의 바이러스를 넣어줄 때 정렬하는 방법에서 상당히 큰 시간복잡도를 요구해서 아슬아슬하게 해결했는데, list를 만든 후에 이를 정렬하고 queue에 넣어주는 방법으로 시간복잡도를 상당히 줄일 수 있다는 것을 알게 되었다. 그래서 이를 적용해 시간복잡도를 줄일 수 있었다.

from collections import deque

N, K = map(int, input().split())
data = []
for i in range(N):
    data.append(list(map(int, input().split())))
S, X, Y = map(int, input().split())

temp = []
for i in range(N):
    for j in range(N):
        if data[i][j] != 0:
            temp.append([data[i][j], i, j])
temp.sort()
queue = deque(temp)
#print(queue)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

before = 0
after = 0
info = 0
while queue:
    count, x, y = queue.popleft()
    after = data[x][y]
    if before == K and after == 1:
        info += 1
    if info == S:
        break
    before = data[x][y]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:
            if data[nx][ny] == 0:
                data[nx][ny] = count
                queue.append([data[nx][ny], nx, ny])
    #print(queue)
print(data[X - 1][Y - 1])