백준 1647 도시 분할 계획 문제 풀이
백준 1647 도시 분할 계획 문제 풀이
백준 온라인 저지, 1647번: 도시 분할 계획
도입
제거할 도로를 선택하는 것과 남길 도로를 선택하는 것은 본질적으로 같으므로 제거할 도로를 선택할 대신 남길 도로를 선택하는 것으로 생각할 수 있다.
위와 같이 생각하면 단순히 가중치가 제시된 연결선에서 몇 개의 연결을 선택하여 최소한의 가중치 합을 갖는 트리, 즉 최소 비용 스패닝 트리를 구하는 것으로 접근할 수 있다.
문제 풀어보기
주의할 점은, 연결을 적절히 제거하여 합이 최소인 두 최소 비용 스패닝 트리를 생성해야한다는 것이다.
1
2
3
4
5
6
7
8
9
10
11
...
conns: int = 0
...
for route in routes:
if conns == n - 2:
break
...
if find(a) != find(b):
merge(a, b)
costs += c
conns += 1
1197 최소 스패닝 트리 문제에서 사용한 프림 알고리즘을 사용하면 가중치가 낮은 간선부터 차례대로 탐색하게 되므로, 적절한 시기에 처리하는 것으로 전체 가중치 합이 최소인 두 최소 비용 스패닝 트리를 생성할 수 있다.