BOJ 1647 도시 분할 계획

N개의 node와 그 node들을 연결하는 M개의 양방향 edge가 있는 그래프가 존재하는데, 이것을 분할해서 2개의 그래프로 만들려고 하는데, 한 그래프내에서는 모든 정점들이 한 그래프내의 다른 정점들까지의 경로가 있어야하고 두 그래프의 간선의 가중치의 합이 최소가 되도록 해야한다. 그래프를 2개로 나누면서 필요없는 간선은 없앨 수 있다.

결국 이렇게 2개의 그래프를 만들고 두 그래프의 간선의 가중치의 합의 최소값을 구하는 문제인데, 딱 보면 Minimum Spanning Tree문제인 것 같아보인다. 그렇다면 그래프를 2개로 나누고 각각 MST를 구해야할까? 그렇게 되면 그래프를 2개로 나누는 경우의 수가 너무 많아지고 그래프를 나누는 것 자체도 까다로울 것 같다. 아예 처음 그래프에서 MST를 구하고 MST에서 가장 가중치가 큰 edge를 없애버리면 어떨까? 확실히 가장 간단해보인다.

근데 이러면 최소인게 보장이 될까? 간단히 생각해보면, 만약 이렇게 나눴을 때의 MST가 먼저 두 개의 그래프로 나눈 후 구한 MST와 다를 수 있을까? 모양은 다를 수 있다해도 edge의 합의 최소값이 다를 수 있을까? 만약 먼저 두 개의 그래프로 나눈 후 구한 MST가 있다고 해도 어차피 그 두 MST를 연결하는 간선은 존재할 수 밖에 없고(모든 점이 다 연결되있었다면) 그 간선의 값만 추가하면 원래 그래프의 MST값이 나온다. 그리고 MST알고리즘을 내가 잘 아는 건 아니지만 생각해보면 모양이 좀 다르게 나올 수는 있어도 구성하는 간선의 가중치 값들이 다를 수는 없어보이고, 그렇기에 그 중 간선의 최대 가중치도 항상 똑같을 것 같다.

내가 증명은 확실히 못하겠지만 직관적으로는 이 풀이가 맞는 것 같아보인다. 일단 백준님 풀이도 푸는 방법은 이렇게 나와있다.

출처 : 백준님 강의, 백준님 강의 자료