https://leetcode.com/problems/cat-and-mouse
- 일단 드디어 Game 문제(MiniMax)를 어느정도 이해한것 같다.
- 여튼 졸라 어렵다..
- MiniMax는 기본적으로 그래프 탐색이고, 경우의 수들을 Tree로 재구성 해야한다.
- 따로 점수내는 알고리즘이 없다면 대충 이런 식이다.
- 내 턴에서 모두 상대방이 이긴다면, Lose를 리턴
- 내 턴에서 하나라도 내가 이기는 수가 있다면, win을 리턴
- 나는 어찌저찌 DP로 짜봤는데, TLE가 났다.
- 문제는 (cat, mouse, turn)으로 그래프를 구성하면 사이클이 발생한다는 점이다. 사이클이 발생한것 까지는 좋은데, 각 플레이어 별 턴을 구성하면 Draw 판단시 문제가 된다.
- 이 기준으로는 Draw를 판단하는게 어렵다. 상황이 반복되는 것을 찾아야 하는데 사이클 경로로 들어가면 무조건 반복된 선택이 만들어진다.
- 사이클 경로로 먼저 들어가서 Draw로 기록되어 버리면, 다음 턴에 상대가 이길 수 있는데에도, 사이클로 잘못 기록된 Draw를 보고, 비길수 있는 수가 있다고 판단한다.
- 해결 방식은 Node의 단위를 (cat, mouse, turn)으로 탐색하되, topological order로 탐색하는것, 이러면 사이클은 가장 나중에 탐색하게 된다.
- 다른 하나는 Node의 단위를 (Cat, mouse)로 가정하고 그래프를 구성하는 것이다.
- 이러면 무승부 판단이 쉬워진다. 양쪽을 동시에 판단하므로 “다음 턴에 상대가 이길 수 있는데에도, 사이클로 잘못 기록된 Draw를 보고, 비길수 있는 수가 있다고 판단” 하는 멍청한 짓을 안하게 된다.
- A와 B를 동시에 플레이 한 후.
- A가 이기는 수가 있음 -> A의 승리
- A가 이기는 수가 없는데, B가 이기는 수가 있음 -> B의 승리
- 둘다 이기는 수가 없음 -> 비김