[Python] 백준 16884 나이트 게임

문제 링크 : https://www.acmicpc.net/problem/16884

 

1. 접근 방법

모든 경우의 수를 탐색하기에는 너무 경우의 수가 많았다.

최대 10,000이지만, n일 때 결과가 n + 1일 때 결과 및 과정에 직접적인 인과 과정을 찾을 수 없었기 때문에, DP 식의 풀이 과정은 옳지 않다고 생각했다.

만약 각각 과정을 백트레킹으로 계산할 수도 있지만, 최대 100개의 테스트 케이스가 주어지면 불가능할 것이라 생각했다.

 

 

2. 풀이 코드

🖥python 코드 : https://github.com/mintropy/baekjoon_py/blob/master/16000/16884.py

GitHub - mintropy/baekjoon_py

📕코드 해설

모든 칸을 다 확인 할수는 없지만, n = 4일 때 정도까지는 다양한 경우의 수를 확인해보았다.

이후에 각 n에 대한 관계를 찾지 못해, 일반적인 상황에서 어떻게 적용될지를 고민했고, 다음과 같은 결론이 나왔다.

 

1) 모든 경우에 0 ~ 8칸에 영향을 줄 수 있다. (나이트를 놓지 못하는 칸)

2) 하나 이상의 나이트가 놓여 있을 때, (거의) 모든 경우에 영향을 줄 수 있는 칸을 1 ~ 8칸 줄일 수 있다.

    거의 모든 경우라고 표현한 것은 확실하게 확인하지는 못했지만, 위와 같이 생각해도 큰 모순이 없다고 생각했기 때문이다.

3) 그리고 결론적으로 n이 짝수라면 후 플레이어가, 홀수라면 선 플레이어가 이기게 된다.

 

3)에 대한 추가 설명을 하면 다음과 같다.

- 만약 n이 홀수라고 하면, 전체 칸의 수도 홀수이다.

홀수개 칸이 남아있다고 하면, 선 플레이어가 항상 마지막 칸에 놓을 수 있다.

만약에 후 플레이어가 짝수개 칸에 놓을 수 있는 상태로 행동을 했다면, 선 플레이어는 짝수개 칸을 남겨서 후 플레이어에게 넘길 수 있다. (1과 2에 의하여)

따라서 항상 후 플레이어는 짝수개 칸일 때 놓게 되고, 마지막 칸은 선 플레이어가 놓을 수 있다.

- 만약 n이 짝수라고 하면, 전체 칸의 수도 짝수이다.

홀수일때와 마찬가지로, 칸의 수가 짝수개이면 후 플레이어가 마지막으로 놓을 수 있다.

모든 경우의 수에서 선 플레이어의 선택에 상관없이, 즉 턴을 넘기며 놓을 수 있는 칸을 짝수 개, 홀수 개로 하는 것과 상관없이, 후 플레이어는 항상 선 플레이어에게 짝수개 칸으로 넘겨줄 수 있고, 선 플레이어는 항상 칸의 수가 짝수 개일 때 행동을 하게 된다.

결과적으로 후 플레이어가 항상 칸의 수가 홀수 개 일때 행동을 하고, 마지막 칸을 놓을 수 있다.

 

어찌 보면 말장난 같을 수도 있지만, 찬찬히 진행해보면 이해할 수 있을 것이다.

 

 

3. 생각 정리

게임이론 문제는 DP 방식으로 해결하는 문제와 이렇게 논리적인 과정으로 해결하는 문제가 있는 것 같다.

이번 문제와 비슷한 유형은 쉽게 해결할 수 있지만, 그 과정과 결과를 한번 더 생각하고 고민하는 게 그만큼 중요하다고 생각한다.