문제 링크
- http://icpc.me/3419
문제 출처
- 2011 CERC D번
사용 알고리즘
- 이분매칭
풀이
격자 그래프는 이분 그래프입니다. 각 격자들을 $i+j$의 기우성에 따라 L, R그룹으로 나눠준 이분 그래프를 생각해봅시다.
일반성을 잃지 않고, 시작 위치가 L그룹에 있다고 생각합시다.
Alice는 자동차를 L그룹에서 R그룹으로 이동시키는 행동을, Bob은 R그룹에서 L그룹으로 이동시키는 행동을 반복할 것입니다. 그러다가 이동을 시킬 수 없는 사람이 지게 되겠죠.
이분 그래프 문제니까 이분 매칭을 생각해볼 수 있습니다.
극단적인 상황을 가정해서, 최대 매칭의 크기가 $\vert L \vert$인 경우를 생각해봅시다. Alice가 처음에 R그룹으로 이동을 할 수 있다면 Alice가 항상 이길 것입니다. Bob이 어느 곳으로 이동을 하든, 이동을 시킨 곳은 최대 매칭 위에 있게 되므로 Alice는 다시 R그룹으로 이동을 할 수 있습니다.
위와 같은 가정이 없는, 일반적인 상황에서는 시작하는 정점을 포함하지 않는 최대 매칭을 Bob이 찾으면 Bob이 이기고, 그렇지 않으면 Alice가 이깁니다.
시작하는 정점을 포함하지 않는 최대 매칭을 찾지 못한 경우를 먼저 생각해봅시다.
위에서 말했던 최대 매칭의 크기가 $\vert L \vert$인 경우와 비슷합니다. Alice가 최대 매칭을 따라 이동하면 항상 이기게 됩니다.
Bob은 최대 매칭에 속하지 않은 정점으로 이동할 수 없습니다. Bob가 최대 매칭에 속하지 않는 정점으로 이동을 시킨다고 하면, 이동한 경로가 Bob의 위치(매칭 포함) -> 매칭1 -> 매칭2 -> ... -> 매칭K -> 매칭 미포함 정점형태가 될텐데, 간선들의 매칭 여부를 뒤집어주면 시작점을 포함하지 않는 매칭을 찾을 수 있기 때문입니다.
시작하는 정점을 포함하지 않는 최대 매칭을 찾은 경우를 생각해봅시다.
Alice는 처음에 어떻게 이동을 하더라도 시작하는 정점을 포함하지 않는 최대 매칭 안으로 이동하게 됩니다. 그러면 Bob는 최대 매칭을 따라 이동하면 항상 이깁니다.
Alice가 최대 매칭에 포함되지 않은 정점으로 이동한 경우를 생각해보면, 이동한 경로가 Alice가 이동한 위치(매칭 미포함) -> 매칭1 -> 매칭2 -> ... -> 매칭K -> 매칭 미포함 정점형태가 될텐데, 간선들의 매칭 여부를 뒤집어주면 매칭 개수가 증가하기 때문에 가정에 모순됩니다.
구현은 생각보다 간단하게 할 수 있습니다.
주어진 그래프에서 이분 매칭을 해주고, 각 정점의 답을 구할 때 현재 정점을 제외한 최대 매칭을 찾을 수 있는지 dfs 한 번으로 확인해주면 됩니다.