CERC 2011. Racing Car Trail

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

격자 그래프가 주어질 때, 갔던 정점을 다시 들리지 않는 조건으로 First와 Second가 번갈아 움직인다. 움직일 수 없는 사람이 질 때, 각각의 정점을 시작점으로 했을 때, 각각의 정점에서 누가 이기는지를 출력하면 된다.

격자 그래프는 이분 그래프다. 정점을 두 집합으로 쪼개서, 현재 정점이 속한 집합을 A, 반대 집합을 B라고 하자. 이 문제의 답은 이분 그래프의 최대 매칭과 관련이 있다.

설명을 돕기 위해, 먼저 매칭 크기 == |A| 인 경우를 생각해 보자. 이 때는 First가 A에서 매칭된 B의 정점으로만 움직여주면, 항상 이길 수 있다. B가 어떻게 움직이든간에, A 집합에 있는 정점으로 다시 가게 될 것이고, 그 정점은 매칭에 속하기 때문에, A는 계속해서 움직일 수 있다. 고로 이 전략을 사용하면 A는 질 수 없다.

이제 이러한 가정 없이 조금 더 일반적인 경우를 생각해 보자. 일반적인 경우에는, First가 시작하는 정점을 포함하지 않는 최대 매칭을 Second가 찾는다면, Second가 이긴다. 그렇지 못했다면, First가 이긴다. 

먼저 First가 시작하는 정점을 포함하지 않는 최대 매칭을 Second가 찾았을 때를 생각해보자. First가 어떻게 움직이든지, First의 다음 위치는 Second의 최대 매칭에 포함될 것이다. (그렇지 않다면 매칭이 늘어날 것이기 때문) Second는 이제 현재 노드에 매칭된 A쪽 정점으로 움직여주면 된다. First가 만약에 다음에 B의 최대 매칭에 포함된 정점으로 움직인다면, Second는 그것을 반복해주면 되기 때문에, Second가 이기게 될 것이다. 

First가 B의 최대 매칭에 포함되지 않는 정점으로 움직이면 되지 않느냐고 물을 수 있다. 애석하게도 그럴 수 없고, 그 이유는 다음과 같다. First가 B의 최대 매칭에 포함되지 않은 정점으로 움직였을 때를 생각해 보면, (매칭 아님 -> (매칭1 - 매칭1) -> (매칭2 - 매칭2) ... -> (매칭N - 매칭N) -> 매칭 아님) 의 형태로 체인이 형성됨을 알 수 있다. 매칭 N개를 전부 끊고, 매칭 아닌 두 정점을 이으면, N+1 크기의 매칭을 찾을 수 있다. 최대 매칭이라는 가정에 모순인 고로 First는 B의 최대 매칭에 갖혀있을 수밖에 없다. ㅠㅠ 고로 First가 시작하지 않는 정점을 포함하지 않는 최대 매칭이 존재하면, Second가 이긴다.

이제 First가 시작하는 정점을 포함하지 않는 최대 매칭이 없을 때를 생각해 보자. 이 때는 맨 처음 매칭 크기 == |A|일 때와 비슷하게, First가 A에서 계속 최대 매칭을 따라서 B 쪽으로 이동시켜주면 항상 이길 수 있다. Second는 B에서 어떻게 이동하든간에, 최대 매칭에 속하지 않은 A의 정점으로 움직일 수가 없는데, 이유는 위와 비슷하다. 만약에 ((매칭1=시작점 - 매칭1) -> (매칭2 - 매칭2) ... -> (매칭N - 매칭N) -> 매칭 아님) 과 같은 경로가 존재하면, 1 - 2, 3 - 4 형태의 매칭을 전부 끊고 2 - 3, 4 - 5 형태로 이우주면, First가 시작하는 정점을 포함하지 않는 최대 매칭이 존재한다. 가정에 모순이므로 Second는 항상 A로 움직이더라도 최대 매칭에 속하게 되며, 고로 A는 앞서 언급한 전략을 유지할 수 있다. 이로써 모든 증명이 끝난다.

이제 문제를 해결하는 방법에 대해서 고민해 보자. 초기 최대 매칭은 이분 그래프니 O(N^3 ~ N^4) 정도에 찾을 수 있고, 어떠한 정점을 포함하지 않는 최대 매칭이 있는지를 빠르게 찾아야 한다. 그냥 하면 Hopcroft-Karp를 사용했다고 했을 때 O(N^5) 의 시간이 소모되므로 더 빠른 풀이를 찾는 것이 좋을 것이다. 

일단 해당 정점이 매칭에 속하지 않는다면 그것으로 끝나니, 해당 정점이 매칭에 속한다고 가정하자. 해당 정점에 연결된 매칭을 지우고, 원래 연결되었던 정점이 짝을 찾을 수 있는지를, 이분 매칭과 똑같은 방식으로 dfs를 사용해서 찾아준다. 이 과정을 각각의 정점에 대해서 반복하면, O(N^4) 시간에 문제를 해결할 수 있다.