[백준][BOJ14621] 나만 안되는 연애

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

14621번: 나만 안되는 연애

---

2. 풀이 : Kruskal

---

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

---

4. 설명

모든 대학교를 최단 거리로 연결을 해야 하는 문제다. 단, 문제의 조건에따라 남초 대학교와 여초 대학교를 연결하는 도로로만 최단 거리가 구성되어야 하고 모든 대학교를 연결하는 경로가 없을 경우 -1을 출력한다.

그림[1]

그림[1]에서 남초 대학교는 파란색으로 여초 대학교는 빨간색으로 표시를 하였고, 각 간선의 가중치는 두 학교간의 거리이다. 간선의 가중치가 작은 순서로 MST를 생성한다. 가중치가 3으로 가장 작은 C학교와 D학교 사이의 도로는 여초 대학교간의 도로이므로 연결할 수 없다. 그 다음으로 가중치가 작은  B학교와 D학교 사이의 도로도 여초 대학교간의 도로이므로 연결할 수 없다. 다음으로 B학교와 E학교의 도로는 남초 대학교와 여초 대학교 사이의 도로이므로 연결이 가능하다.

그림[2]

이를 반복하여 그림[3]과 같이 MST를 생성하며, 이 때 연결된 거리의 합이 최단 거리가 된다.

그림[3]

그림[4]와 같이 A대학교가 여초 대학교라면, 모든 대학교를 연결하는 경로가 존재하지 않는다. 모든 대학교를 연결하는 경로가 존재하지 않는다는 의미는 MST가 생성되지 않는다는 의미이므로, MST의 특징에 따라 연결된 도로의 갯수가 '대학교 수 - 1'개인 4개보다 작게된다.

그림[4]

따라서, 문제의 조건에 따라 Kruskal 알고리즘으로 MST를 생성하며, 연결된 도로의 갯수가 '대학교 수 - 1'개 보다 작다면 -1을 출력하고 그렇지 않다면 연결된 모든 도로의 합을 출력한다.

---

5. 코드