[BOJ] 경쟁적 전염(18405) 문제 풀기 | Python3

---

문제 풀이)

 BFS로 문제를 풀었습니다. 바이러스가 작은 순 부터 증식되므로 초기 큐에 [바이러스종류, x좌표, y좌표] 리스트를 바이러스종류가 작은 순으로 정렬하여 넣습니다. 매 초마다 큐에 있는 좌표에 대해 상하좌우로 증식을 해야하므로 탐색 전 현재 큐의 길이만큼 반복문을 실행하여 좌표를 꺼내 상하좌우 좌표를 탐색하며 0이면 해당 좌표를 바이러스종류 숫자로 변경합니다. queue 가 빌 때까지 반복하여 바이러스를 증식시키지만, 우리가 알고싶은 건 s초의 특정 좌표의 값이므로 반복문 실행이 s번 될 때 while 문을 종료합니다. 

 

코드)

from collections import deque
 
def bfs(graph, x, y, s, n):
    dx=[-1,1,0,0]; dy=[0,0,1,-1]
    queue=deque(sorted([(graph[i][j],i,j) for i in range(n) for j in range(n) if graph[i][j]!=0]))
    
    count=0
    while queue:
        if count==s: break
        for _ in range(len(queue)):
            virus, curx, cury=queue.popleft()
            for i in range(4):
                nx, ny = curx+dx[i], cury+dy[i]
                if 0<=nx<n and 0<=ny<n and graph[nx][ny]==0:
                    graph[nx][ny]=virus
                    queue.append([virus,nx,ny])
        count+=1
    return graph[x-1][y-1]
            
if __name__=="__main__":
    n, k = map(int, input().split())
    graph=[list(map(int, input().split())) for _ in range(n)]
    s, x, y = map(int, input().split())
    print(bfs(graph, x, y, s, n))