혜아랑은 옛날부터 팀을 하기로 얘기가 되어 있었다. 2학기 개강 직전에 태평소국밥 (유성 홈플러스 근처에 있고 개꿀맛임) 에서 민규랑 팀을 하기로 최종 합의를 봤다. 예전부터 "지훈이나 민규 둘 중 하나" 라고 얘기를 했고 그래서 팀원을 말하기 참으로 눈치 보이는 상황이었는데 그때 마침 청하 한병을 깐 상황이어서 그냥 얘기해 버렸다. 팀명은 내가 지었고, 괜찮은가에 대해 고민을 아주 많이 했으나 이건 PC보다는 표현의 자유라고 생각해서 확정했다. 적당히 논란이 있어야 좋은 팀명이라는 나의 관종같은 철학이 반영되었다
그 이후 팀 연습은.. 세보니 7번 했다. 다들 바쁘고 시간이 잘 안 겹쳐서 저 정도면 열심히 잡았다고 생각.. 방학 때 최대한 열심히 할 계획이다. 크게 말린 적은 없고, 가끔 상당히 좋은 성적이 나와서 만족스러웠다. 연습하면서 옛날 고려대의 Let Myungwoo go WF랑 비슷한 성향의 팀이 아닌가 생각이 들었다. WF 진출에 대해서는 우리가 굉장히 유리한 고지에 있어서 충분히 자신이 있었다. 그래서 나는 대회 전에 긴장이 되거나 부담이 되거나 뭐 그러진 않았다.. 잠은 못 잤지만. 물론 대전 대회는 굉장히 진지하게 임했다. 11문제 푼 거에 대해서 "대충 하신 거 아니에요?" 라고 물으시는 분들도 계셨는데, 저희는 팀 연습이건 언제건 진지하게 합니다!
연습 세션 날에는 카이스트 팀 대부분 + 홍콩 해외 팀 (EC라 외침은 아니다) 이 광세족발하고 설빙을 갔다 왔다. 광세족발은 진짜 개꿀맛. 홍콩 팀은 내가 아는 친구가 한 명 있어서 끼워줬고 광세족발에서 술도 같이 먹고 돌아갔다 (...) 당연히 많이는 안 먹었다.
대회 때는 AJ를 제외한 모든 문제가 쉽게 풀이가 나와서 디버깅 외에는 특별한 discussion 없이 혼자 혼자 잘 풀었던 것 같다. 거의 개인전... 다만 B하고 L에서 많이 말렸다. L을 민규가 보고 O(PN^3M) 풀이를 찾았는데, 난 딱 보니까 O(M^3lgM)이 떠올랐고 M <= 4N이니 당연히 4승보다 3승로그인 후자가 더 빠를 것이라 생각해서 이걸 짰다. TLE를 받았고 상수최적화를 하다가 나중에 잘 계산해 보니까 O(PN^3M)은 돌고 O(M^3lgM)은 안 돌 수도 있는 사이즈임을 깨달음 (...) 여기서 시간하고 페널티를 많이 버렸다. 그거 아니었으면 900 초반대의 페널티가 나왔을 것 같다. 앞 10개를 푼 후 A를 합심해서 해결하고, J를 합심해서 못 해결하고 (ㅠㅠ) J는 랜덤으로도 뚫린다고 하는데 시도해 볼걸 그랬다 ㅠㅠ
셋은 전반적으로 쉬운 편이었는데, 심지어 경쟁이 엄청나게 치열한 대회였다. 두 면에서 모두 대전 리저널 역대급이다. 114분에 MolaMola가 11솔브, 153분에 ACGTeam이 올솔브를 띄웠으며, 프리즈는 115분에 진행되었다. 이 상황을 보고 나는 2010 대전의 로얄로더가 떠올랐는데 (사실 어린이라 잘 모르고 구전으로만 들었다) 이번에는 심지어 그런 팀이 2팀.. 관중석에서는 3시간 쯤에 누가 월파를 나가는지를 확정했다고 하는데 이후에 엄청 지루했을 것 같다. 경쟁의 여파로 시상식 때 분위기가 상당히 험악했다... 나한테 작년 대전은 정말 잊을 수 없는 추억이었는데, 올해는 재밌는 부분이 많이 사라져서 아쉬움이 많이 남았다 ㅠㅠ 에밀리아도 없었다
대회 이후에는 뒷풀이를 갔고 여기선 정말 즐거웠다. 오랜만에 과음을 해서 다음 날 고생을 하긴 했지만 ㅋㅋ
Solution Sketch
스탠딩이나 개인적인 생각을 종합해서 대충 난이도 순으로 정렬했다. 이견이 있을 수 있다.
솔직히 말해서 쉽고 어렵고를 떠나서 문제가 그렇게 재밌지는 않았다 ㅠ A / E / J / K는 좋은 문제고, 뒷쪽에 쓴 문제들이 전반적으로 더 재미있다. I는 잘 알려진 유형인데 처음 봤으면 신기할 것이다.
D. Happy Numbers
f(n) <= 729이기 때문에 숫자는 빠르게 루프에 진입한다. 증명은 안 해도 되지만 비둘기집의 원리를 사용하면 된다. f(n)을 구현한 후, 루프에 진입할 때까지 계속 돌려주고 그 루프가 1 -> 1 -> 1.. 의 형태인지 확인해 주면 된다.
Dictionary 형태의 자료 구조 (배열, std::set 등등) 를 사용하면 현재 루프에 진입했는지를 확인할 수 있으니, 진입했을 때 1인지만 체크해 주면 된다. 아니면, 한 1000번 정도 n = f(n)을 대입한 후 그게 1인지를 확인해도 된다. 여하튼 쉬운 문제이고, 다양한 풀이가 있다.
C. Game Map
degree가 증가하는 방향으로만 움직일 수 있으니, DP를 사용해서 쉽게 계산할 수 있다. DP[i] = (i번 정점에서 시작하는 최장 경로) 라 정의하자. $adj(i)$ 를 $i$에서 갈 수 있는 정점의 집합이라 할 때, $DP[i] = Max_{j \in adj(i)}(DP[j] + 1)$ 이다. 사이클이 없는 방향성 그래프(DAG)이기 때문에 이러한 DP가 잘 정의되어서 답을 구할 수 있다. 모든 DP 값 중 최대를 출력하면 된다.
F. Philosopher's Walk
재귀적으로 생각하면 편하다. $N * N$ 격자 Hilbert curve에서의 $X$번째 위치를 찾을 때, 위치를 바로 찾는다 생각하지 말자. 대신, 어느 4분면에 있는지를 찾은 후, $(N/2) * (N/2)$ 격자 Hilbert curve에서 위치를 찾고, 그 위치 값을 변형시키면 된다.
어느 사분면에 있는지는 $X \leq N^2 / 4$, $N^2 / 4 < x \leq N^2 / 2$ ... 에 따라 결정되니, 4개의 케이스를 나눈 후 재귀 함수를 사용해서 답을 구하면 된다.
H. Rock Paper Scissors
길이 $m$의 문자열은 $[0, m-1], [1, m], \cdots, [n-m, n-1]$ 과 같이 $n-m+1$가지 경우의 위치에 배치할 수 있다. 각각의 배정에 대해서 바위 -> 가위, 가위 -> 보, 보 -> 바위가 몇 번 만나는 지를 세고, 센 값을 더하면 각 위치에 문자열을 넣었을 때의 이기는 횟수를 셀 수 있다. 이 값을 모두 계산하면 원하는 값을 다 계산할 수 있다.
일반성을 잃지 않고 바위 -> 가위 케이스만 고려한다고 하자. $L[i] =$ (첫번째 문자열의 $i$번 문자가 가위), $R[i] =$ (두번째 문자열의 $i$번 문자가 바위) 이제 $A[i] = [i, i+m-1]$ 위치에 길이 $m$의 문자열을 배치했을 때의 매칭 수라고 하면, $A[i] = \sum_{j=0}^{m-1}(L[i+j] * R[j])$ 가 성립한다. R을 뒤집으면 $A[i] = \sum_{j = 0}^{m-1}(L[i+j] * R[m-1-j])$ 가 되어, Convolution을 구하는 문제로 환원되고, 이는 빠른 푸리에 변환(FFT)으로 구할 수 있다.
인터넷 예선에 출제된 Telescope랑 아주 유사한 문제니, 빠른 푸리에 변환에 대한 추가적인 정보는 링크를 참조하자.
G. Rectilinear Regions
각각의 x좌표 구간($[x, x+1]$) 에 대해, L strip과 U strip의 현재 y좌표를 배열에 저장할 수 있다. 이 값을 $L[x], U[x]$ 라 하자. 그러면 우리가 구하는 것은 $L[x] < U[x]$인 $x$의 연속 구간의 개수와, 그러한 구간에서의 $U[x] - L[x]$ 합임을 알 수 있다. 이는 단순 루프로 쉽게 계산할 수 있다. 다만 $x = -\infty, x = \infty$ 영역과 붙어 있는 연속 구간은 제거해야 하니 예외 처리를 해 주자.
구현 팁은 x좌표에 모두 10 정도를 더한 후, [0, 50020] 구간에 대해서 문제를 해결하는 것이었다. 0과 붙어 있는 연속 구간과 50019와 붙어 있는 연속 구간을 처음에 마킹해 준 후, 마킹 안 된 연속 구간에 대해서 문제를 풀면 된다.
K. Untangled Chain
어떻게 바꿔도 겹치지만 않으면 되니까, 주어지는 길이에 대해서는 전혀 신경 쓸 필요가 없고 그냥 움직이는 방향만 신경쓰면 된다. 세로 선분에서 가로 선분으로 방향이 바뀌는 상황이라고 하자. 어떠한 점에서 선분을 뻗어나갈 때, 항상 그 선분이 뻗어나갈 수 있는 충분한 공간을 제공할 수 있게 하면 좋을 것이다.
현재 세로로 $i$번 선분을 그었고, 가로로 새롭게 $i+1$번째 선분을 그으려 하는 상황이라 하자. $i+1$이 향하는 방향이 왼쪽이라면 (지금까지 출력한 모든 X좌표 중 최소) - 1, 오른쪽이라면 (지금까지 출력한 모든 X좌표 중 최대) + 1 까지 선분을 쏘자. $i+2$에서 세로 선분을 쏘았을 때 그 선분은 지금까지 봤던 모든 위치보다 왼쪽 / 오른쪽에 있기 때문에 이후 다른 선분이랑 겹칠 일이 없고, 나 역시 $i-1$번째 선분을 그었을 때 그러한 가정으로 그었기 때문에 $i+1$번째 선분을 문제 없이 그을 수 있다. 가로 - 세로의 경우에는 반대로 하면 된다.
B. Connect3
가능한 상태 수를 단순하게 분석하면 빈 칸 / 검은 돌 / 흰 돌 의 세 경우라 3^16 = 4300만 가량이다. 하지만 잘 생각해 보면 한 세로 줄에 쌓여있는 돌의 개수는 0개 ~ 4개이고, 각 돌은 흰 돌이거나 검은 돌이기 때문에 $2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 31$ 개의 상태가 존재한다. 31^4 = 100만 가량이기 때문에 모든 상태를 부족함 없이 돌 수 있다. 고로, 한번 방문했던 상태를 다시 방문하지 않게 하는 백트래킹을 구현하면 문제를 해결할 수 있다.
가능한 입력이 많아야 64가지이기 때문에, 로컬에서 모든 입력에 대해서 답을 구한 후 단순히 이 답을 배열에 저장해서 출력하게 시킬 수도 있다. 만약 시간 제한이 모자라다는 느낌이 들면 이러한 방법을 사용할 수 있다.
I. Slot Machines
전체가 사이클이라고 생각하고 문제를 해결한다. $S$의 prefix이면서 동시에 suffix인 최대 길이 문자열을 $f(S)$ 라 하자 ($S \neq f(S)$ 를 가정해야 한다. 아니면 너무 자명하게 $f(S) = S$가 되니..) 답은 $|S| - |f(S)|$이고, 이유는 다음과 같다.
* 그보다 작은 사이클은 존재할 수 없다. 그러한 것이 존재했다면 $f(S)$보다 더 긴 부분 문자열을 찾을 수 있기 때문이다.
* $C = |S| - |f(S)|$ 길이의 사이클이 존재한다. prefix와 suffix가 같기 때문에, $S[i] = S[i + C]$ 가 항상 성립하기 때문이다.
이 때 $f(S)$의 길이, 즉 $|f(S)|$는 KMP 알고리즘을 통해서 $O(N)$에 구할 수 있다. 이를 $S$의 "Failure function" 이라 부른다. 이 알고리즘에 대해서는 http://koosaga.com/156 등의 글을 참고하라.
이제, 원래 문제로 돌아가자. 원래 문제에서는 랜덤한 부분이 초기에 존재하고, 이 부분을 지워야 한다. 즉 모든 suffix에 대해서 failure function을 전부 구해야 한다. 한편, failure function은 $S$를 뒤집건 말건 똑같기 때문에, 문자열 전체를 뒤집으면 모든 prefix에 대해서 이를 전부 시행하는 것으로 바뀐다. KMP 알고리즘을 사용하면 모든 prefix의 failure function을 $O(N)$에 구할 수 있다. 고로 전체 문제가 $O(N)$ 에 풀린다.
L. Vacation Plans
호텔은 $i -> i$로 가는 가중치 $H_i$의 간선으로 보면 편하고, 사람이 2명 이하라면, 1번 정점에 공항과 0원짜리 호텔을 짓는 식으로 사람을 한 명 더 만들어 줄 수 있다. 이렇게 되면 사람의 수가 3명으로 고정되고, 각 사람이 매일 이동을 해야 하니 구현이 편하다. 이 가정하에 다른 아이디어의 두 가지 풀이를 소개한다.
풀이 1. O(PN^3M) 동적 계획법
항상 집에서 공항으로 가는 경로가 있으니, 단순히 생각하면 매일 매일 공항 방향으로 움직인 후 먼저 도착한 사람이 쉬는게 최적이라고 볼 수 있다. 이렇게 보면 사람들이 적어도 $max(N_1, N_2, N_3)$일 안에 만날 것이라는 직관을 받을 수 있다. 하지만, 실제로는 집에서 공항으로 $N$일 안에 만날 수 있더라도 훨씬 나중에 만나는 게 더 작은 값을 줄 수도 있다. 예를 들어, 모든 간선의 가중치가 0이지만 호텔들은 말도 안되게 비싸고, 첫번째 사람은 공항을 도는 길이 7, 두번째 사람은 길이 11, 세번째 사람은 길이 13의 사이클이 있다고 생각하자. 만약에 각 사람들이 공항에 도착한 날짜가 다르다면, 최대 LCM(7, 11, 13) = 1001일까지 기다려야지 최적이 될 수 있다.
그렇다고 하더라도, 정말 사람들이 만나는 시간의 한도가 없을까? 매일 매일, 사람들의 상태는 (사람 1의 위치, 사람 2의 위치, 사람 3의 위치) 의 tuple로 결정할 수 있다. 최단 경로를 탔다고 하면, 매일 매일 이러한 사람들의 상태는 다를 것이다 - 그렇지 않다면, 어떠한 상태를 다시 방문했다는 뜻이고, 그 사이에 했던 행동이 의미가 없기 때문이다. 가능한 상태의 개수는 $N_1 * N_2 * N_3$이니, 결국 $N_1 * N_2 * N_3$일 안에 만나는 최단 경로가 존재함을 알 수 있다. 이 값은 125000일 정도이다.
이제 동적 계획법을 사용해서 문제를 해결할 수 있다. $DP[i][j][k] =$ (i일 후 j번 국가의 k번 도시에 도착하는 최소 비용) 과 같은 동적 계획법을 정의하자 (벨만 포드와 매우 유사하다). 이 테이블을 모두 채운다면 $i$일에 공항에서 모이는 최소 비용을 모두 계산할 수 있다. 메모리가 부족할 수 있는데, $DP[i]$가 $DP[i-1]$에만 영향을 받는 것을 생각하면 토글링을 사용하여 문제를 해결할 수 있다.
풀이 2. O(PMN^2lgM) 다익스트라
다른 풀이로는 Dijkstra's Algorithm을 사용한 풀이가 존재하며, 풀이 1에서 언급한 "사람들의 상태" 를 직접적으로 이용해서 그래프를 만드는 방식이다. 사람들의 상태를 (사람 1의 위치, 사람 2의 위치, 사람 3의 위치)로 볼 수 있고, 각 사람이 움직이는 것을 상태 전이로 볼 수 있다. 다음 날이 되면, 사람 1과 사람 2와 사람 3이 동시에 다른 정점으로 움직인다. 이렇게 만든 그래프에서 다익스트라를 돌리면 정점이 $O(N^3)$, 간선이 $\sum_{i \in V(G_1)}{deg_i} * \sum_{j \in V(G_2)}{deg_j} * \sum_{k \in V(G_3)}{deg_k} = O(M^3)$ 이라 $O(M^3lgM)$ 정도의 시간 복잡도가 드는데, 이는 1초 안에 돌지 않는다.
이 때, 간선의 개수를 줄여서 이를 최적화할 수 있다. 세 사람의 상태를 한꺼번에 바꾸는 대신, "턴"을 두어서 첫번째를 바꾸고, 두번째를 바꾸고, 세번째를 바꾸고... 와 같이 순차적으로 바꾸는 것이다. 세번째 사람의 위치까지 바뀌면, 모든 턴이 끝났으니 하루가 지나고 첫번째 사람이 상태를 바꿔야 한다. 이렇게 되면 상태에는 "현재 턴"을 나타내야 하기 때문에 $O(PN^3)$ 개로 늘어나지만, 간선의 수는 $O(PMN^2)$ 로 줄어들고, 고로 시간 안에 문제를 해결할 수 있다.
E. How Many To Be Happy?
어떠한 에지 $e = \{u, v\}$ 를 최소 스패닝 트리에 넣을 수 있다는 것은, $e$보다 cost가 작은 에지들로 $u$에서 $v$를 이을 수 없다는 것을 뜻한다. 크루스칼 알고리즘을 생각해 보면 이것이 필요 충분 조건임을 쉽게 알 수 있다. 즉, 각각의 에지 $e$에 대해서 $e$보다 cost가 작은 에지들을 최소 몇개 제거해야 $u$와 $v$를 이을 수 없는지를 판단하면 된다.
이는 그래프의 "최소 컷" 개념을 알면 쉽게 구할 수 있다. $e$보다 cost가 작은 에지들을 가지고 그래프를 만든 후, 이 그래프에서 $u$와 $v$의 최소 컷을 구해야 한다. Maximum flow Minimum cut theorem에 의해, 최대 유량을 구함으로써 최소 컷을 구할 수 있고, Ford-Fulkerson을 사용하면 $O(nm)$ 에 최대 유량을구할 수 있으니 $O(nm^2)$에 답을 찾을 수 있다. 어떤 유량 알고리즘을 사용하여도 충분히 시간 안에 작동할 것이다.
Dinic's Algorithm을 사용하면 이를 $O(mn^{5/3})$까지 줄일 수 있다. 유량 알고리즘에 대해서 자세히 알고 싶다면 이 글을 참고하면 좋다.
A. Broadcast Stations
문제를 해결하는 데 아주 중요한 사실이 존재하는데, 바로 두 기지국이 덮는 영역이 겹치지 않는 최적 해가 존재한다는 것이다. 만약에 어떠한 최적해에서 두 기지국 $v, w$이 덮는 영역이 겹친다고 생각해 보자. $p(v) + p(w) \geq dist(v, w)$ 이라는 것인데, $v$에서 $p(w)$만큼 떨어진 위치에 $p(v) + p(w)$ 비용의 기지국을 세우면, 원래 덮는 것보다 더 많은 영역을 같은 비용으로 덮을 수 있다. 이런 식으로 기지국의 개수를 줄여나가다 보면 결국 언젠가는 겹치지 않는 순간이 오게 될 것이고, 고로 증명이 종료된다.
이 Lemma가 워낙 강력한 것이라서, 이를 사용한 아주 간단한 풀이가 있을 거라고 짐작하고 있다. 하지만 대회 시간에는 이를 찾지 못했고, 대신 naive한 DP를 최적화하는 전략을 사용했다. 이에 대해서 설명한다.
Lemma를 토대로 $O(N^3)$ 동적 계획법을 유도할 수 있다. 먼저 두 정점 $s, t$간의 거리 $dist(s, t)$를 전처리하자 ($O(N^2)$ DP로 가능.) 편의상 1번 정점을 루트로 하는 rooted tree라고 생각하자. $DP[i] = (i$번 정점을 루트로 하는 서브트리를 덮는 최소 비용) 이라 하자. $i$번 정점을 덮는 기지국의 위치 $v$를 고정시키고, $p(v)$를 $dist(i, v)$에서 $n-1$까지 모두 시도하면 $O(N^2)$ 가지의 경우가 있다. 각각의 경우에 대해서 덮이지 않는 서브트리가 나오는데, 두 기지국의 영역이 겹치지 않기 때문에 서브트리에 대해서 문제가 독립적이다. 각 독립적인 영역 역시 서브트리 형태이기 때문에 동적 계획법으로 구할 수 있다. 이렇게 하면 한 DP 테이블을 채우는 데 $O(N^3)$ 시간이 걸린다... 고 생각할 수 있겠지만, $p(v)$를 고정시켰을 때 더하게 되는 DP 테이블은 $v$ 에서 거리가 정확히 $p(v)+1$이며 $i$의 서브트리에 존재하는 정점들이다. 고로 $v$를 고정한 후 이를 카운팅하는 식으로 하면 $O(N^2)$ 시간에 한 DP 테이블을 채울 수 있다.
한편, 루트가 아닌 모든 정점 $i$는 $parent(i) - i$ 를 잇는 에지가 존재하는데, 위 DP 과정을 잘 상기시켜보면, 어떠한 정점 $v$를 놓았을 때 이 정점은 $i$는 덮지만 $parent(i)$ 는 덮지 않게 될 것임을 알 수 있다. 고로, 루트가 아니라면 $p(v) = dist(v, i)$ 로 설정해야 하는 power가 고정된다. 이 점을 활용해서, 루트가 아닌 모든 정점에 대해서 $O(N)$ 시간에 DP 테이블을 채워 보자.
$DP[i]$를 채울 때, 모든 서브트리에 대해서 $Cand[j] = (j$를 루트로 했을 때 더하게 될 DP값 합)으로 정의하자. $i$의 서브트리 정점 $k$를 다 돌면서 $Cand[]$ 배열에 어떻게 변화를 주는지를 생각해 보자. 먼저 $dist(i, k) = 0 (mod 2)$ 라면 $dp[k]$를 $dp[i]$에 더할 일은 없으니 패스. 그렇지 않다면, $k$의 $(dist(i, k) - 1) / 2$ 번째 조상을 $w$ 라 하자. $dp[k]$는 $parent(w)$를 루트로 하는 서브트리에는 모두 더해지고, $w$를 루트로 하는 서브트리에는 더해지지 않는다. 서브트리에 값을 더하는 것은 결국 DFS preorder 구간에 값을 더하는 것이니 변홧값 배열로 가능하다. 만약 또 다른 DP를 통해 정점 $v$의 $k$번째 조상을 전처리 했다면, 총 $O(N)$에 $Cand[]$ 배열을 채울 수 있다. 이를 통해 루트가 아닌 정점의 DP값을 $O(N)$에 구할 수 있어서 총 $O(N^2)$ 에 문제가 해결된다.
$O(N)$ 에 문제를 풀 수도 있다. 이 부분은 대략 다음과 같이 유도할 수 있다.
* 1. 두 기지국이 덮는 영역이 겹치지 않으며, 기지국을 하나의 노드로 했을 때 트리가 path가 되는 최적 해가 존재한다.
* 2. 주어진 트리의 임의의 지름에 대하여, 해당 지름 위에 모든 기지국이 존재하고, 두 기지국이 덮는 영역이 겹치지 않는 최적 해가 존재한다.
각 부분에 대한 증명은 상당히 messy한 고로 생략한다. 저걸 알면 나름 간단한 동적 계획법으로 문제를 해결할 수 있다.
J. Strongly Matchable
MolaMola팀의 cki86201이 풀이를 알려줬다. 그래프가 Strongly Matchable인지를 확인하는 데 다음 Lemma가 아주 큰 도움이 된다. 디스크립션에 나와있고 구사과 블로그에도 나와있는 홀의 정리에 대한 지식이 있음을 가정한다.
Lemma. $G$는 $2N$개의 정점으로 이루어진 연결 그래프라 하자. 이 때 $A, B \subset V(G), |A| + |B| > N, A \neq \emptyset, B \neq \emptyset, A \cap B = \emptyset$ 을 만족하는 모든 정점의 부분집합 $A, B$ 에 대해서, $A$와 $B$를 잇는 간선이 하나라도 존재하는 것과, $G$가 Strongly Matchable한 것이 동치이다.
Proof. (역방향) $G$가 Strongly Matchable하다면, $A, B \subset V(G), |A| + |B| > N, A \neq \emptyset, B \neq \emptyset, A \cap B = \emptyset$ 을 만족하는 모든 정점의 부분집합 $A, B$ 에 대해서, $A$와 $B$를 잇는 간선이 하나라도 존재한다. 그렇지 않은 부분집합 $A, B$가 존재한다고 하자. 만약 $|A| > N$이나 $|B| > N$을 만족한다면, 이 중 $N$개를 아무거나 뽑고 다 지워서 크기를 $N$ 이하로 만들어 주자. (그래도 간선이 없고 $|A| + |B| > N$)
$G$에서 $2N$ 개의 정점을 $L$과 $R$로 partition할 때, $A \subset L, B \subset R$이 되도록 partition할 수 있다. 이 때, $|A| + |B| > N$ -> $|A| > N - |B| \geq |N(A)|$를 만족해서, 홀의 정리에 의해서 이 partition에서 완벽 매칭이 존재하지 않는다. 고로 가정에 모순이다.
(정방향) $A, B \subset V(G), |A| + |B| > N, A \cap B = \emptyset$ 을 만족하는 모든 정점의 부분집합 $A, B$ 에 대해서, $A$와 $B$를 잇는 간선이 하나라도 존재한다면, $G$는 Strongly Matchable하다. $G$에서 $2N$개의 정점을 $L$, $R$로 partition했다고 하자. $A \subset L$ 이며 $|A| > |N(A)|$ 인 subset이 있다고 하면, $B = R \setminus N(A)$ 라 두었을 때 $A$와 $B$를 잇는 간선이 존재하지 않으며 $|A| + |B| = |A| + N - |N(A)| > N$ 을 만족한다. 고로 가정에 모순이다. 즉, 모든 $A \subset L$ 에 대해 $|A| \geq |N(A)|$ 를 만족하며, 홀의 정리에 의해 어떠한 partition에서도 완벽 매칭이 존재한다.
Lemma는 연결 그래프에 대해서만 정의를 했는데, 연결 그래프가 아니라면 어떻게 될까? 그래프에는 2개 이상의 컴포넌트가 있고 그 중 하나는 정점의 수가 $N$개 이하이다. 이를 한쪽 side에 넣고 partition을 하면, 이 컴포넌트에서 다른 컴포넌트로 가는 에지가 전혀 없기 때문에 자명히 완벽 매칭이 존재하지 않는다. 고로 연결 그래프가 아니면 -1을 찍어주고 시작한다. 고로 $G$가 연결 그래프임을 가정해도 괜찮다.
이제, $A, B \subset V(G), |A| + |B| > N, A \neq \emptyset, B \neq \emptyset, A \cap B = \emptyset$을 만족하는 정점의 부분집합 $A, B$ 중 $A$와 $B$를 잇는 간선이 하나도 존재하지 않는 것이 있으면, $G$는 Strongly Matchable하지 않다. 이런 $A, B$를 어떻게 찾을까? 실제로 이는 Vertex Cut을 의미한다. $X = V(G) \setminus A \setminus B$ 라는 집합을 고정시키자. $G \ X$가 연결되지 않았다면 $A, B$를 찾을 수 있지만, 그렇지 않다면 $A, B$를 찾을 수 없다. 또한, $|A| + |B| > N$이어야 하기 때문에, $|X| < N$ 이어야 한다.
이제 문제를 더 단순화 시킬 수 있다. 우리는 그래프에서 최소의 점을 제거해서, 그래프를 disconnect시켜야 한다. 이 때 만약 $N-1$개 이하의 점으로 그래프를 disconnect시킬 수 없으면 그래프는 Strongly Matchable하다. 최소의 간선을 제거해서 그래프를 disconnect시키는 문제는 최근 블로그에서 다루었던 Global Min-Cut 문제인데, 여기서는 정점을 제거해야 하니 문제가 조금 다르다.
일단, 두 정점의 연결을 끊는 Vertex s - t Min-Cut을 어떻게 푸는지 리뷰해 보자. 이것도 이 블로그에 있다. 각각의 정점을 in(V), out(V)로 이은 후, in(V) -> out(V)를 잇는 유량 1의 간선을 만들고, 모든 간선 S - E에 대해서 out(S) -> in(E)로 가는 유량 $\infty$의 간선을 추가하자. out(s) 와 in(t)의 Edge min-cut을 구하면 그것이 Vertex s - t min-cut임을 알 수 있다.
이를 Global Min-Cut으로 바꾸기 위해서는, $A$에 속하는 임의의 정점 $s$, $B$에 속하는 임의의 정점 $t$를 고정시키는 것 말고는 방법이 없다. Edge min-cut에서는 Gomory-Hu Tree등의 전략이 먹혔지만, 여기서는 그래프 빌딩이 다르기 때문이다. 고로 모든 $O(N^2)$ 쌍에 대해서 민 컷을 구해주고, 이 중 $N-1$ 이하의 민 컷이 존재하는지를 판별해야 한다. 이렇게 하면 시간 복잡도는 $O(N^5)$ 인데 그냥 디닉 쓰면 시간 안에 잘 도는 것 같다..
