[백준 1647번] 도시 분할 계획

난이도: 골드 4

문제 링크: www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

기본적인 크루스칼 알고리즘을 사용하고, 약간의 아이디어를 내서 최소 신장 트리를 두 개로 분할하는 문제입니다.

크루스칼 알고리즘에 대한 자세한 내용은 그래프 이론 글의 크루스칼 알고리즘 파트를 참고해 주세요.

 

최소 신장 트리에 대해 다시 복습해 봅시다.

모든 노드가 연결되어 있으며, 그 연결된 값의 총합이 최소가 될 때 최소 신장 트리라고 부릅니다.

그렇다면 두 개의 최소 신장 트리로 나누려면 어떻게 하면 될까요?

트리에서 가장 값이 큰 간선을 지우면 됩니다. 이렇게 하면 트리가 두 개로 분할되며, 분할된 트리가 각각 최소 신장 트리가 됩니다.

 

따라서 문제에서는 기본적인 크루스칼 알고리즘을 구현하고, 트리를 두 개로 분할해 주면 됩니다.

 

코드 상에서는 50번 줄에 max_cost = max(max_cost, cost) 라고 하였지만, 벡터는 이미 cost를 기준으로 정렬이 되어 있으므로, max_cost = cost 라고 작성해도 무방합니다.

 

p.s.

2달 전과 오늘 같은 문제를 풀었습니다.

크루스칼 알고리즘을 복습할 겸 이 문제를 풀게 되었는데, 두 달 전에 제가 같은 문제를 풀었었습니다.

2달 전의 제 코드를 보니까 훨씬 지저분하고, 비효율적이네요. 위의 수행 시간만 봐도 차이가 큽니다.

스스로 발전하고 있다는 뜻으로 생각하니 기분이 좋네요!