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

아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로 그램을 작성하세요. (경로가 없으면 Impossible를 출력한다) ▣ 입력설명 첫째 줄에는 정점의 수 N(1 arr[now]) continue; // 비용 확인 후 갱신 : a가 있는 배열로 들어가서 b,c확인 for(Point p : graph.get(now)) { if(arr[p.dot] > nowCost + p.cost) { // 갱신 후 최소비용으로 offer arr[p.dot] = nowCost + p.cost; pQ.offer(new Point(p.dot, nowCost + p.cost)); } } } } public static void main(String[] args) { Dijkstra T = n..