Pragmatism

문제 링크: https://oj.uz/problem/view/KAISTRUN26SPRING_F

지난 RUN 봄대회에 출제된 ibm2006의 문제다. 정해가 매우 아름다워 풀이 공개 시간에 박수를 받은 문제이기도 하여 소개한다.

문제

정점이 $n$개인 그래프 $G$와 $k \leq \frac{n}{2}$인 양의 정수 $k$가 주어진다. 이때 아래 둘 중 하나를 찾아라.

• 크기가 $k$인 $X, Y \subseteq V(G)$. 단, $X$와 $Y$ 사이에는 간선이 없다.
• $P_{n-2k+2}$-subgraph

풀이

$G$ 위에서의 DFS 과정을 생각하는데, 각 정점이 방문되는 순서만 보는 것이 아니라 정점에 방문하거나 탐색을 끝나고 정점에서 돌아 나오는 각 과정을 한 단위 시간으로 생각하자(말을 한 칸씩 이동한다고 보면 된다). 이때 각 시간마다 아래 세 집합을 정의할 수 있다.

• 한 번도 방문되지 않은 정점의 집합 $A$
• 방문되었으나 아직 탐색이 끝나고 돌아 나오지 않은 정점의 집합 $B$
• 탐색이 끝나고 돌아 나온 정점의 집합 $C$

이때 쉽게 관찰 가능한 정보는 다음과 같다.

1. $A$와 $C$ 사이에 간선이 있다면 해당 간선을 남긴 채로 $C$의 정점에서 탐색이 끝났다는 뜻이 되므로 모순이다. 따라서 $A$와 $C$ 사이에는 간선이 없다.
2. $B$는 현재 DFS 진행 과정 중에 ‘살아 있는’ 줄기이므로 시작점으로부터의 path를 이룬다.
3. 새로운 정점에 방문할 때는 $A$의 크기가 1 줄고, 정점에서 돌아 나올 때는 $C$의 크기가 1 늘어난다.
4. DFS가 시작하기 전에는 $|A| = n, |C| = 0$이며 DFS가 끝난 후에는 $|A| = 0, |C| = n$이다.

3번과 4번의 관찰을 통해 $|A| = |C|$인 시점이 존재함을 알 수 있다. 이때 $|A| = |C| = x$라고 하자. 만약 $x \geq k$라면, $A$와 $C$의 크기 $k$인 임의의 부분집합을 택하여 $X, Y$로 둘 수 있다. 이때 1번 관찰에 의해 $X$와 $Y$는 올바른 답이 된다. 만약 $x < k$라면, $|B| = n-|A|-|C| \geq n-2(k-1) = n-2k+2$이다. 2번 관찰에 의해 $B$는 $P_{n-2k+2}$-subgraph를 가짐을 알 수 있다.

구현은 매우 짧은 편이다. 구현 시 주의할 점은 $G$가 connected라는 조건이 없기 때문에 각 component에 대해서 DFS를 돌리면서 $A$, $B$, $C$는 global하게 관리해야 한다는 점이다.