boj 1647 : 도시 분할 계획

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

 

최소 비용의 간선으로 두 마을을 나누는 문제이다.

MST(Minimum Spanning Tree)를 약간만 응용하면 가능한 문제이다.

 

MST를 푸는 두 알고리즘 중, 크루스칼 알고리즘으로 MST문제를 해결하다가 말면 성공적으로 도시를 분할할 수 있다.

집의 개수가 N개라면 가장 적은 비용의 N-1개의 간선만 연결한다면 모든 집을 최소 비용으로 연결할 수 있다.

여기서, 1개만큼 간선을 덜 연결하면, 즉 N-2개만큼의 간선을 연결하면 2그룹의 마을로 나누어지면서 문제가 해결된다.

 

문제에서는 언급하지 않았지만, 좀더 나아가 3그룹, 4그룹의 마을로 나누기 위해서는 어떻게하면 좋을까?

마찬가지로 N-3, N-4개의 간선만 연결하면 3그룹, 4그룹의 마을로 나누어진다.