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

오늘은 백준(BOJ) 1647번 도시 분할 계획 문제에 대해 다뤄볼 예정이다.

도시 분할 계획 문제 링크 (백준(BOJ) 1647번 문제): https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

문제 설명

백준 1647번 도시 분할 계획 문제는 하나로 구성된 마을을 두 마을로 분리시키려고 하는데, 길의 유지비를 최소화하여 두 마을로 분리하려고 한다. 각 노드와 간선의 가중치가 주어질 때, 길에 사용되는 최소한의 유지비를 출력하는 문제이다. 

 

문제 풀이

백준 1647번 도시 분할 계획 문제는 최소 스패닝 트리 문제로 크루스칼 알고리즘(Kruskal algorithm)을 사용해주면 된다. 크루스칼 알고리즘(Kruskal algorithm)을 구현할 때, 그래프에 사이클이 존재해서는 안되므로 Union Find 방식으로 사이클이 생기지 않도록 해주는 것이 중요하다. 만일 시간 초과가 날 경우, 두 마을을 분리하려고 할 때, (Connected Component)를 구성하는 그래프에 모든 노드가 연결 되었을 때 break를 걸어주면 시간 초과 문제를 해결할 수 있을 것이다. 

 

위 내용을 기반으로, 아래와 같이 코드를 구현하였다.