BOJ 17962 Game on a Tree + BOJ 3419 Racing Car Trail

이 문제에서는 SEERC '19 Game on a Tree와 CERC '11 Racing Car Trail의 풀이를 다룬다. 풀이의 첫 단어부터 강력한 스포일러가 될 수 있으니 충분한 고민을 해보고 오는 것을 권한다. 풀이 설명 또한 두 문제의 context에 의존하는 경향이 강하니 지문을 숙지하고 오자.

 

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

17962번: Game on a Tree

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

3419번: Racing Car Trail

풀이

17962가 사실상 3419의 부분문제가 된다. 따라서 이 글에서는 3419를 먼저 풀이한다.

 

3419번 풀이

 

Proposition 0. 3419의 그리드 그래프는 Bipartite graph이므로 최대 매칭을 구하기가 쉽다. 17962의 이상한 그래프 역시 dp로 최대 매칭을 쉽게 구할 수 있다.

 

Theorem 1. 게임의 시작점을 x라고 하자. x를 포함하는 완전 매칭이 존재한다면 선수 (A)가 승리한다.

 

pf. 선수가 어떤 점에 있든 자신의 매칭 파트너로 이동하면 된다. 후수 (B)는 어떤 점을 고르더라도 아직 사용되지 않은 점으로 이동할 수밖에 없다.

 

편의상 매칭에 의해 선택된 간선을 '켜진' 간선, 그렇지 않은 간선을 '꺼진' 간선이라고 부른다.

 

Definition 2. Alternating path 중 양 끝 간선이 모두 꺼진 간선을 augmenting path라고 한다. 그렇다면, 양 끝 간선 중 정확히 하나만 꺼진 경로를 replacing path라고 부르자.

 

사실 replacing path는 길이가 짝수인 alternating path와 동치이지만 별로 중요하지 않다.

최대 매칭에는 augmenting path가 존재하지 않지만, replacing path는 얼마든지 존재할 수 있다.

 

Remark 3. Replacing path에서 꺼진 간선을 켜고, 켜진 간선을 꺼도 매칭의 크기는 변하지 않는다. 

 

Theorem 4. 시작점 x가 매칭 파트너를 갖지 않는다면 (matching - free) 선수가 패배한다.

 

pf. 게임을 진행하면서 선수가 matching - free 정점 y에 도달했다고 하면 x - y 자체가 augmenting path가 되어 최대 매칭임에 모순이다. 따라서 선수가 어디로 가든 그 점은 매칭 파트너를 갖고, 후수는 계속 매칭을 따라 움직이면 된다.

 

Theorem 5. 시작점 x가 매칭 파트너를 갖는다고 하자. 만약 어떤 matching - free 정점 y가 존재해서 x와 y를 잇는 replacing path가 존재한다면 선수가 패배하고, 그렇지 않다면 선수가 승리한다.

다시 말해, (x를 포함하지 않는 최대 매칭이 존재) ⟺ (선수의 패배).

 

pf. ⟹는 Theorem 4에 의해 자명.

⟸) 당연히 대우로 x를 포함하지 않는 최대 매칭이 없으면 선수가 승리하는 것을 보인다. 이 명제는 Theorem 1의 일반화로, 마찬가지로 선수는 매칭을 따라 움직이면 승리한다. 이 전략이 실패하는 경우는 어쩌다 matching - free에 도달하는 경우뿐인데, 이 경우 이동 경로 자체가 replacing path가 되어 모순.

 

이제 승리 조건을 알았다. 남은 건 시간복잡도와 구현.

 

이분그래프이기 때문에 Hopcroft - Karp를 써도 되지만, 간선이 \(O(V)\)개 뿐이므로 Ford-Fulkerson같은 원시적인 방법을 써도 \(O(V^2)\) 안에 돌아간다.

 

남은 건 모든 \(V\)개의 정점에 대해 replacing path를 찾아주는 일인데 이건 DFS 한 방에 \(O(V + E)\)로 해결 가능. 따라서 시간복잡도는 \(O(V^2)\)이 되고, \(V = O(N^2)\)이므로 \(O(N^4)\)에 문제를 해결할 수 있다.

 

17962번 풀이

이 경우는 시작점을 선수(Alice)가 고르고, 후수(Bob)가 이동을 시작하는 경우다. 따라서 matching - free인 점이 하나라도 존재하면 Alice가 그 점을 선택해서 이기고 (Theorem 4), 완전 매칭이 존재하면 Bob이 이긴다. (Theorem 1)

 

dp[v] = v가 루트인 서브트리에 남아있는 matching - free 정점의 개수로 두면 남은 풀이는 기계적.