BaekJoon18405_경쟁적 전염

문제

풀이

bfs를 사용해서 문제를 풀면 되지만 바이러스가 퍼지는 순서가 정해져 있으며 정해진 시간만큼만 퍼진다는 조건 때문에 조금 까다로웠다.
1. 가장 초기상태의 바이러스 위치들을 입력받는다.
2. 바이러스 숫자, x좌표, y좌표를 입력받고 바이러스 숫자에 맞춰 정렬한다.
3. 그 정렬한 리스트를 큐에 넣는다.
4. 그대로 bfs를 진행하는데 바이러스의 숫자가 작은 순서대로 퍼지면서 시간이 정해져 있기 때문에 check 변수를 두고 각 초마다 한번 넣었을 때의 큐의 크기 만큼만 퍼지게 한다.
-> for _ in range(len(queue) 부분
이 부분을 처음에 생각해내기가 힘들었다.

상세히 얘기하면
3 3
1 0 2
0 0 0
3 0 0
2 3 2
이렇게 주어졌을 때 첫번째에 queue = ((1,0,0), (2,0,2), (3,2,0)) 이 주어지고 3만큼 루프를 돌면 queue = ((1,0,1), (1,1,0), (2,1,2), (3,2,1)) 이 되고 이후에도 계속해서 바이러스의 숫자 순으로 퍼지게 된다.

풀이 코드

from collections import deque

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

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

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

dx = [-1,1,0,0] 
dy = [0,0,-1,1]


            
check = 0
def bfs(s):
    first = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] > 0:
                first.append((graph[i][j],i,j))
    queue = deque(sorted(first,key = lambda x : x[0]))
    check = 0
    while queue:
        if check == s:
            break
        for _ in range(len(queue)):
            virus, x, y = queue.popleft()
            for i in range(4):
                mx = x + dx[i]
                my = y + dy[i]
                if mx >= n or mx < 0 or my >= n or my < 0:
                    continue
                if graph[mx][my] == 0:
                    graph[mx][my] = virus
                    queue.append((virus,mx,my))
        
        check += 1

        
    
    

bfs(s)

print(graph[x-1][y-1])