해설
문제에서 모든 마을 안의 집들은 연결되어야 하며, 그 간선의 비용이 최소가 되어야한다고 한다.
집들끼리 연결만 되어있다면 길을 없앨 수 있다고 한다. 즉, 모든 노드 간 연결만 되어있다면 어떻게든 간선을 없애도 된다.
이쯤 보면 눈치를 챘을 것이다. 전형적인 MST 구하기 문제이다.
단 문제에서 추가적인 조건으로 마을을 2개로 나눠야한다는 조건이 주어졌다.
어떻게 나누면 좋을까? 이는 문제를 풀면서 한번 알아보자.
일단 MST를 구하는 문제이므로 Union&Find와 크루스칼 알고리즘을 이용한다.
- 간선정보를 저장하는 배열을 만들고, 이 배열을 간선의 가중치 순으로 오름차순 정렬한다.
- 간선배열을 하나씩 탐색하며 간선에 연결된 start와 end노드가 같은 집합에 속해있지 않다면, 사이클이 형성되지 않아 연결이 가능하다는 의미이므로 Union 해주고 해당 간선을 채택한다.
- 이렇게 하면 전체 MST에 대한 가중치 합이 나올 것이다.
하지만, 여기서 우리는 추가적으로 2개의 MST를 만들어야한다.
- 최적의 상태인 하나의 MST가 이미 만들어져있고, 이걸 나눈다면 최적인 상태의 2개의 MST가 나올 것이다.
- 즉, 현재 MST에서 가장 높은 가중치를 갖는 간선 하나를 끊어버린다.
- 그렇게 되면 자동으로 Spanning Tree 2개가 생성된다.
문제의 조건에서 마을 안에는 집 하나 이상만 존재하면 되기 때문에 이렇게 하는 것이 가능하다.
문제에서 주어진 예제를 통해 한번 보자.
빨간색 간선들로 만들어진 것이 하나의 MST이고,
여기서 가장 최대 값을 갖는 간선인 {start:6 end:7 weight:4}를 끊어버리면
[1,2,3,4,5,6] 마을과 [7] 마을 2개가 형성된다.
MST를 만들고, MST의 가중치 합 - 간선 중 최대 값의 가중치를 하면 되는 것이다.
구현
MST의 가중치 합을 구할 때마다 채택된 간선의 최대값을 갱신에서 저장하고
마지막에 그 최대값을 가중치합에서 빼주면 된다.
성장하는 프런트엔드 개발자