백준 8193 킹세종 (POI 2009/2010 stage 2 Teleportation)

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

한국어 지문에 사소한 오류가 있는데, 1번 정점과 2번 정점은 항상 연결되어있다는 조건이 빠져있다.

 

문제를 간단히 요약하면,

가중치 없는 무향 그래프 $G = (V, E)$가 주어질 때, 간선을 최대한 많이 추가해야한다. 단 이때 1번 정점과 2번 정점 사이의 최단거리가 5 이상임이 유지되어야 한다.

 

보통 우리는 자료구조를 다룰 때 간선을 삭제하는 것 보다 추가하는 것이 쉽기에 이를 활용하는 경우가 많다. 그러나 이 문제의 경우엔 완전그래프에서 간선을 최소한으로 삭제하는 문제로 생각해주는 것이 편하다.

 

문제를 다음과 같이 환원하자. 완전그래프와 지워지면 안되는 간선의 집합이 주어졌을 때, 간선을 최소한으로 삭제하여 1번 정점과 2번 정점의 최단거리가 5 이상을 만족하도록 해보자.

 

이때 우리는 최단거리가 5 미만인 경로만 고려해주면 되고, 길이가 1인 경로, 2인 경로, 3인 경로, 4인 경로를 모두 고려하여 각 경로가 존재하지 않도록 만들어보자. 5는 굉장히 작은 숫자이기에, 이러한 접근은 자연스럽다.

 

길이가 1인 경로는 $1 \rightarrow 2$ 하나 밖에 없고, 이 간선은 지울 수 있을테니 지우면 된다.

 

길이가 2인 경로는 어떤 정점 $x$에 대해 $1 \rightarrow x \rightarrow 2$를 만족하는 경로일 것이고, $1 \rightarrow x$ 또는 $x \rightarrow 2$를 지워줘야 할 것이다. 이제 그럼 이러한 간선들을 다 지웠을 때 그래프가 어떤 모양일지 생각해보자. 

$1$번 정점과 이어져있는 정점들의 집합을 $A$, $2$번 정점과 이어져있는 정점들의 집합을 $B$라 하자. 그럼 기존의 그래프가 완전그래프였기에, $1$번 정점과 $A$ 사이에 간선은 $|A|$개 존재하고, $A$와 $B$ 사이에 간선은 $|A| \cdot |B|$개 존재하고, $B$와 $2$번 정점 사이에 간선은 $|B|$개 존재한다. 

 

이제 길이가 3, 4인 경로들을 고려해줘야 하는데, 잘 생각해보면 이러한 경로들은 모두 $1$번 정점과 $A$사이에 간선과 $2$번 정점과 $B$사이의 간선을 이용하기에, 이를 최대한 삭제하는 것이 좋다. 입력으로 주어진 (즉, 삭제하면 안되는) 그래프의 정점 $1$과 $2$의 차수를 생각해보자. $|A| \geq deg(1), |B| \geq deg(2)$를 만족해야 한다. 그래프를 다시 구성해보면,

이때 $S$는 $1$번 정점도, $2$번 정점도, $A, B$에도 속하지 않는 정점들의 집합이다. $|A| = deg(1), |B| = deg(2)$를 만족하도록 그래프를 구성했을 때의 얘기이다. $A$와 $B$를 잇는 간선들(경로가 3인 경우)를 모두 지워주자. 이제 $S$에서 $A$ 또는 $B$로 가는 간선 중 하나를 지워야 하는데, 이는 $s \in S$에 대해 $s$와 연결된 삭제되면 안되는 간선들의 경우 모두 $A$와 이어져 있거나 $B$와 이어져 있음을 관찰하면, 어렵지 않게 최소한의 간선들만 삭제해줄 수 있다.

 

이때 삭제되는 간선들은 간단한 식으로 표현되기에, 구현 또한 굉장히 짧다.