Search

경쟁적 전염

문제 : 경쟁적 전염

풀이

해결에 필요한 핵심 아이디어: BFS(너비 우선 탐색), 우선순위 큐

해결 시나리오

초기에 주어진 지점들을 시작점으로 BFS 수행
번호가 낮은 바이러스에게 전염 우선 순위가 있으므로 우선 순위 큐를 사용
파이썬의 heapq 활용
전염된 시간을 고려하지 않고 우선 순위가 부여되면 안되므로 큐에 삽입할 튜플은 (시간, 번호, x 좌표, y 좌표)로 구성
time 변수에 업데이트 하면서 S초가 지났을 때 BFS를 멈추고 ,원하는 위치의 값을 출력

시간 복잡도

인접 행렬로 구현한 그래프의 경우,
BFS의 시간 복잡도는 O(N²)이고 최대 번 수행될 수 있으므로 O(N⁴)
heappushO(logN)의 시간복잡도를 가지는우선 순위 큐(heapq)를 사용하므로 최종적으론 O(N³logN) → 시간제한(1초) 무난히 통과
풀이

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.