문제 : 경쟁적 전염
풀이
해결에 필요한 핵심 아이디어: BFS(너비 우선 탐색), 우선순위 큐
해결 시나리오
•
초기에 주어진 지점들을 시작점으로 BFS 수행
◦
번호가 낮은 바이러스에게 전염 우선 순위가 있으므로 우선 순위 큐를 사용
▪
파이썬의 heapq 활용
▪
전염된 시간을 고려하지 않고 우선 순위가 부여되면 안되므로
큐에 삽입할 튜플은 (시간, 번호, x 좌표, y 좌표)로 구성
•
time 변수에 업데이트 하면서 S초가 지났을 때 BFS를 멈추고 ,원하는 위치의 값을 출력
시간 복잡도
•
인접 행렬로 구현한 그래프의 경우,
◦
BFS의 시간 복잡도는 O(N²)이고 최대 N² 번 수행될 수 있으므로 O(N⁴)
◦
heappush에 O(logN)의 시간복잡도를 가지는우선 순위 큐(heapq)를 사용하므로
최종적으론 O(N³logN) → 시간제한(1초) 무난히 통과
풀이
