백준 1647 도시 분할 계획 C++

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

그래프가 주어져 있을 때 최소 스패닝 트리 (MST) 를 만드는 문제입니다. 전체 간선을 오름차순으로 정렬 후, 크루스칼 알고리즘을 통해 최소 스패닝 트리를 만들면 됩니다. 

크루스칼 알고리즘을 이용해 MST를 만들면 모든 마을을 이을 수 있는 최소 경로를 찾을 수 있게 되고 이 때 마지막 가중치를 가지는 간선 (연결 가능한 간선 중 가중치 최대) 인 것을 빼면 두 마을로 이은 것과 동일합니다.

예를 들어,

출발-> 도착 : 가중치 (도착-> 출발 길 존재)

1 -> 2 : 10,

2-> 3 : 20,

3-> 4 : 30,

4-> 2 : 40

이라고 가정하면, 처음에 자신의 부모노드를 자신으로 설정 후, 부모 노드가 서로 다르고 사이클이 발생하지 않으면 이어주면 됩니다.

MST를 1번 노드와 2번 노드부터 시작하면 두 노드는 처음에 부모 노드가 자기 자신이므로 1,2 노드를 잇습니다.

그리고 2, 3 번 노드를 비교하면 3번의 부모노드는 3번, 2번의 부모노드는 2번 이므로 또 두 노드를 잇습니다.

3번과 4번을 비교하면, 3번의 부모노드는 2번, 4번의 부모노드는 4번이므로 둘을 잇습니다.

4번과 2번을 비교하면, 4번의 부모노드는 2번, 2번의 부모노드는 2번이므로 사이클이 발생하므로 이어주지 않습니다.

결과적으로 1->2, 3->2, 4->3 의 경로가 존재하여 모든 노드를 잇는 MST를 만들 수 있습니다. 하지만 이 때 마지막 이어준 간선인 30 가중치를 가지는 3->4 간선을 빼면 1,2,3 을 한 마을, 4를 한 마을로 잡을 수 있습니다. 

 

코드는 다음과 같습니다.