[백준][BOJ1922] 네트워크 연결

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

1922번: 네트워크 연결

---

2. 풀이 : Kruskal

---

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

---

4. 설명

kruskal 알고리즘을 사용하여, 최소 스패닝 트리를 만들어 문제를 해결한다.

그림[1]과 같이 가중치 오름차순 순으로 모든 간선들을 우선순위큐에 삽입한다.

그림[1]

 우선순위큐에서 간선을 하나씩 빼내면서 union-find를 진행한다.

그림[2]

그림[3]

그림[4]

그림[5]

그림[5]에서 1번 컴퓨터와 2번 컴퓨터는 이미 3번 컴퓨터를 통해 연결되어 동일한 네트워크상에 있으므로, 1번 컴퓨터와 2번 컴퓨터는 연결하지 않는다.

그림[6]

그림[7]

그림[7]에서 2번 컴퓨터와 4번 컴퓨터도 이미 동일한 네트워크상에 있으므로 연결하지 않는다.

그림[8]

그림[9]

그림[9]에서 5번 컴퓨터와 6번 컴퓨터도 이미 동일한 네트워크상에 있으므로 연결하지 않는다.

그림[10]

그림[10]에서 3번 컴퓨터와 5번 컴퓨터도 이미 동일한 네트워크상에 있으므로 연결하지 않는다.

그림[11]

그림[11]과 같이 우선순위큐에 더 이상 탐색할 간선이 없으므로 탐색을 종료하고, 그 때의 가중치 합인 23이 모든 컴퓨터를 연결하는데 필요한 최소 비용이 된다.

---

5. 코드