BOJ 10806 - 공중도시

시험기간 탓에 멈춰 있던 Class 9 밀기를 다시 시작했다. 그 동안도 몇 개 푼 문제가 있긴 한데, 좋은 풀이가 많길래 굳이 올리지 않았다.

 

문제 요약

 

무방향 그래프가 주어진다. 이 때, 어느 간선을 제거해도 그래프가 하나의 컴포넌트가 되기 위해 추가해야 하는 간선의 최소 개수를 구하고 실례를 구성하시오.

 

풀이

우선, 제거했을 때 그래프가 나누어지는 간선은 단절선이다. 따라서 단절선이 아닌 간선들은 두 정점을 union한다고 생각하고 그래프를 구성하면 트리가 된다. 단절선만 남긴 그래프이니 이는 당연하다. 단절선을 구할 때 멀티 에지가 들어오는 것만 조심하면 된다.

이제 트리에서 최소한의 간선을 추가해 잘 이어주는 것이 남았다. 개수는 대충 생각해보면 \(\lceil \frac{l}{2} \rceil\) (\(l\)은 리프의 개수)일 것 같고, 실제로도 맞다. 하지만 어려운 것은 실례 구성이다. 막 이으면 https://www.acmicpc.net/board/view/48938 과 같은 경우에서 문제가 생길 수 있다. 어떻게 잘 이어주어야 할까?내가 푼 방법은 다음과 같다. 우선 트리에서 리프가 아닌 정점을 하나 잡자. 그리고 리프를 dfs 순서대로 저장해준 후, \(i\)번과 \(i + \frac{l}{2}\)번 리프를 이어주면 된다. 만약 남으면 아무렇게나 하나 이어주면 된다.이 코드로 맞은 후 혹시 뚫은 것은 아닐까 걱정이 되어 인터넷을 뒤져보았더니, 다행히 증명이 가능한 풀이인 것 같다.https://blog.naver.com/jinhan814/222527400268 여기에 좋은 증명이 있어 대신 첨부한다.

 

클래스 9 문제들은 당연한 것이겠지만 대부분 문제 퀄리티가 매우 좋은 것 같다. 풀이도 그렇고, 디스크립션도 대부분 작위적인 상황이 없이 매우 자연스럽다. 좋은 문제들을 만드는 사람들은 참 대단한 것 같다..