[백준] 22151 Игра (파이썬), 게임 이론

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

22151번: Игра

# 원문 러시아어
# 번역 https://www.acmicpc.net/board/view/101822

룬석 옮기기 게임은 마법사 두 명이서 즐길 수 있는 재밌는 게임이다.

여기 무한한 크기의 좌표평면이 있으며,
이 좌표평면의 좌표 (xs, ys)에 룬석이 놓여 있다. 

마법사 알파와 베타는 턴을 번갈아가면서 룬석을
거리 m 이하로 떨어진 정수 좌표로 옮겨야 한다.
여기서 거리는 맨해튼 거리를 의미한다.
즉, 룬석이 원래 있던 위치를 (x1, y1)라 하고, 옮긴 후의
위치를 (x2, y2)라 했을 때, |x1 - x2| + |y1 - y2| <= m을
만족하여야 한다는 뜻이다.

정해진 위치 (xf, yf)로 룬석을 옮긴 마법사가 게임에서 승리하게 된다. 

알파와 베타는 둘 다 이 게임의 고수이기 때문에, 최선의 전략으로 게임을 한다.
게임의 정보가 주어지면, 여러분은 누가 게임에서 승리할지를 판별하여야 한다.
게임은 알파가 항상 먼저 시작한다. 단, 앞서 말했듯이 알파와 베타는
모두 최선의 전략으로 게임을 하기 때문에, 게임이 영원히 끝나지 않는
경우가 생길 수도 있다. 여러분은 이 경우도 판별해 주어야 한다.

입력
첫째 줄에 테스트 케이스의 수 n이 주어진다.
두 번째 줄부터 (n + 1)줄까지 
m, xs, ys, xf, yf가 차례대로 공백을 사이에 두고 주어진다.

출력
누가 게임에서 이기는 지를 각 테스트 케이스마다
한 줄씩 출력하면 된다. 출력 방법은 아래와 같다.

● 알파가 이기는 경우:
First {turn}

● 베타가 이기는 경우:
Second {turn}

● 게임이 영원히 끝나지 않는 경우:
Infinity

여기서 {turn} 은 게임이 몇 턴 동안 진행되었는지를 의미한다.
마법사 한 명이 룬석을 1회 옮긴 것을 한 번의 턴으로 센다.

 

풀이

경우의 수를 나눠서 첫 번째 턴부터 천천히 생각해보자. 여기서 dist는 맨 처음 시작하였을 때의 현재 돌의 위치와 최종 목적지의 위치의 맨해튼 거리를 의미한다.

Case 1:
dist <= m

이 경우 자명하게 정답은 'First 1'이다.

Case 2:
dist > m

일단 Case 1, Case 2 이외의 경우는 존재하지 않는다. 이걸 염두하고 Case 2를 알아보자. 이때 첫 번째 플레이어가 할 수 있는 선택지는 4가지이다.

1. new_dist = dist+smth
2. new_dist = dist
3. new_dist = dist-smth, such that new_dist > m
4. new_dist = dist-smth, such that new_dist <= m

조금 더 멀리 보내는 1번, 현재랑 동일한 위치로 이동 혹은 가만히 있는 2번, 살짝 가까워지지만 m보다는 먼 3번, 가까워져서 m 이하인 4번.
이때 4번을 하게 되면 2번째 턴에서 2번째 플레이어가 게임을 이길 수 있게 되니 절대로 4번은 하지 않는다.남은 선택지인 1, 2, 3번 중 하나를 선택하게 된다. 그리고 턴을 넘겨준다. 이때 턴을 넘겨받은 두 번째 플레이어는 다시금 Case 2에 해당하는 돌을 넘겨받게 된다.

Case 2:
dist > m

두 번째 플레이어 역시 위와 같은 논리로 다시 1, 2, 3번 중 하나를 선택하고 상대편 플레이어에게 Case 2를 넘겨주게 된다. 이러한 행동을 무한하게 반복하게 된다.

즉, 'Infinity'가 정답이다.

 

정답 코드

import sys
input = sys.stdin.readline
print = sys.stdout.write

n = int(input())
for _ in range(n):
    m, xs, ys, xf, yf = map(int, input().split())
    dist = abs(xs-xf) + abs(ys-yf)
    if dist <= m:
        print('First 1'+'\n')
    else:
        print('Infinity'+'\n')

 

소감

처음 풀어보는 게임 이론 문제인데 익숙하지 않아서 난이도가 브론즈1인 것에 비하면 푸는 데에 상당히 오랜 시간이 걸렸다.