[백준][BOJ1197] 최소 스패닝 트리

1. 문제 : https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

---

2. 풀이 : Prim

---

3. 시간복잡도 : O(ElogV)

---

4. 설명

그림[1]과 같이 주어진 그래프를 인접리스트로 표현한다. 시작점까지의 가중치는 없으므로 시작점의 번호인 7과 가중치 0을 우선순위큐에 삽입한다. 우선순위큐는 가중치의 오름차순으로 정렬한다.

그림[1]

그림[2]와 같이 7번 노드를 방문 처리 후, 7번 노드에서 갈 수 있는 노드의 데이터를 우선순위큐에 삽입한다. 

그림[2]

그림[3]과 같이 2번 노드를 방문 처리 후, 2번 노드에서 갈 수 있는 노드의 데이터를 우선순위큐에 삽입한다.

그림[3]

그림[4]와 같이 3번 노드를 방문 처리 후, 3번 노드에서 갈 수 있는 노드의 데이터를 우선순위큐에 삽입한다.

그림[4]

그림[5]와 같이 4번 노드를 방문 처리 후, 4번 노드에서 갈 수 있는 노드의 데이터를 우선순위큐에 삽입한다.

그림[5]

그림[6]에서 우선순위큐에서 (4, 18) 데이터가 나오지만, 4번 노드는 이미 3번 노드에서 더 작은 가중치인 12로 연결되어 방문처리 되었기때문에 skip을 한다. 그 다음 우선순위큐에서 나오는 5번 노드를 방문 처리 후, 5번 노드에서 갈 수 있는 노드의 데이터를 우선순위큐에 삽입한다.

그림[6]

그림[7]과 같이 이미 방문 처리한 5번 노드는 skip 하고 6번 노드를 방문 처리 후, 6번 노드에서 갈 수 있는 노드의 데이터를 우선순위큐에 삽입한다.

그림[7]

그림[8]과 같이 1번 노드를 방문 처리 후, 1번 노드에서 갈 수 있는 노드의 데이터를 우선순위큐에 삽입한다.

그림[8]

이미 방문 처리한 1번 노드는 skip 하고 우선순위큐에 더 이상의 데이터가 없으므로 탐색을 종료한다. 그림[9]와 같이 탐색을 종료한 시점의 트리가 최소 스패닝 트리가 되며, 그 때의 가중치는 102가 된다.

그림[9]

---

5. 코드