[Algorithm][MST][Prim's algorithm] boj1922 네트워크 연결

---

크루스칼 알고리즘과 Prim's 알고리즘으로 해결할 수 있다. 이걸 MST (Minimal Spanning Tree) 알고리즘이라고 한다.

난 Prim's 알고리즘으로 해결했다.

다익스트라 알고리즘과 유사하지만 '정점으로 가는 최단거리'를 계속 갱신해 줄 필요가 없다.

그리고 다익스트라 알고리즘은 정점을 연결하는 간선의 방향이 존재하는데, MST는 그저 '연결되었는가?' 이다.

pq : 현재 위치에서 갈 수 있는, 혹은 지금까지 갈 수 있었던 정점들을 거리순으로 정렬해 놓는 우선순위 큐

dist : 스패닝 트리를 만드는 최소비용을 누적해나갈 변수

1. 큐에서 하나 빼고 이미 갔던 곳인지 검사한다. 이미 갔던 곳이라면 반복.

2. 이전 위치로부터 현재 위치로 가는 거리를 dist에 추가함.

3. 현재 위치에서 갈 수 있는 정점들을 pq에 담는다.

이걸 우선순위 큐를 비울 때까지 반복.

view code on github