원더랜드(최소스패닝트리 : 프림, PriorityQueue)

최소 스패닝 트리 만드는 방법에는 크루스칼 뿐만아니라 프림 알고리즘도 있습니다. 크루스칼 알고리즘을 Union&Find로 구현하였다면 프림 알고리즘은 PriorityQueue를 사용해서 구현합니다. (직전에 풀었던) 같은 문제를 프림 알고리즘을 통해 구현해보도록 하겠습니다. 설명 원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지 보수하는 재정이 바닥난 것이다. 원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 아래의 그림은 그 한 예를 설명하는 그림이다. 위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다. 입력 첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 ..

2022.04.08