백준 1647 도시 분할 계획 문제 풀이
문제 파악하기
문제는 도로를 제거하여 유지비용을 최소화하는 것이 목표라고 합니다. 제거할 도로를 선택하는 것과 남길 도로를 선택하는 것은 본질적으로 같으므로 제거할 도로를 선택할 대신 남길 도로를 선택하는 것으로 생각할 수 있습니다.
위와 같이 생각하면 단순히 가중치가 제시된 연결선에서 몇 개의 연결을 선택하여 최소한의 가중치 합을 갖는 트리, 즉 최소 비용 스패닝 트리를 구하는 것으로 접근할 수 있습니다.
이 문제와 1197 최소 스패닝 트리 문제는 본질적으로 같으므로 유사하게 풀어갈 수 있습니다.
문제 풀어보기
주의할 점은, 연결을 적절히 제거하여 합이 최소인 두 최소 비용 스패닝 트리를 생성해야한다는 것입니다.
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 최소 스패닝 트리 문제에서 사용한 프림 알고리즘을 사용하면 가중치가 낮은 간선부터 차례대로 탐색하게 되므로, 적절한 시기에 처리하는 것으로 전체 가중치 합이 최소인 두 최소 비용 스패닝 트리를 생성할 수 있습니다.