[BOJ 28218] 격자 게임

게임 이론 문제

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

 

 

---

[문제 풀이]

 

문제를 요약하자면 두 사람이 번갈아 가면서 특정 칸부터 (N, M)까지 오른쪽으로 한 칸씩, 아래로 한 칸씩, 혹은 대각선으로 K칸을 이동하는 게임을 할 때, 첫 번째로 이동하는 사람이 이길 수 있는지 묻는 문제입니다.

 

특정 칸에서 시작해서 무조건 이길 수 있는지 확인하는 것은 상당히 머리가 아픕니다. 생각을 달리 해볼 필요가 있습니다. 직관적으로 떠올릴 수 있도록 위해 예시를 들겠습니다.

N = 6, M = 8, K = 3이고 막힌 칸이 없는 보드를 예시로 보겠습니다.

 

예시 1

 

동그라미가 있는 위치에서 (N, M)으로 이동할 때 누가 이길지 직관적으로 떠올리기는 매우 어렵습니다.

 

 

예시 2

 

하지만 해당 위치에서 (N, M)으로 이동할 때 누가 이길지는 매우 간단합니다. 자신의 차례를 건너뛸 수 없기 때문에 현재 이동해야 하는 사람이 반드시 이기게 됩니다.

 

 

예시 3

 

해당 위치에 있는 사람은 오른쪽으로 이동한다면 패배할 수 있지만, 플레이어는 항상 최선을 다해서 게임을 하기 때문에 대각선으로 2칸 움직여서 바로 (N, M)으로 이동하는 판단을 할 것입니다.

 

 

예시 4

 

예시 2, 3을 통해 위 5개 위치에 있다면 반드시 이긴다는 것을 알 수 있습니다. 이제부터 현재 움직여야 하는 플레이어가 반드시 이길 수 있는 위치를 필승 위치라고 하겠습니다.

 

아주 직관적으로 생각할 수 있는 부분은 여기까지입니다. 여기서 생각을 조금 더 해본다면, 현재 움직여야 하는 플레이어가 필승 위치로 이동하지 않는다면 반드시 지는 상황은 모면할 수 있습니다. 그렇다면 현재 움직여야 하는 플레이어가 움직일 수 있는 모든 위치가 필승 위치인 경우, 해당 플레이어는 반드시 패배하게 됩니다. 그리고 이제부터 그런 위치를 필패 위치라고 하겠습니다. 

 

 

예시 5

 

작은 동그라미로 표현한 위치가 필패 위치입니다. 지금까지 생각해 본 내용으로는 더 이상 할 수 있는 것이 없어 보입니다. 하지만 여기서 한번만 더 생각해 보겠습니다. 현재 움직여야 하는 플레이어가 필패 위치로 이동할 수 있다면 상대를 반드시 지게 만들 수 있습니다. 다르게 말해서, 필패 위치를 통해서 필승 위치를 만들어낼 수 있는 것입니다.

 

 

이제부터는 예시 4와 같은 상태를 저장하고 다이나믹 프로그래밍을 이용하여 필승 위치와 필패 위치를 기록하면 됩니다. 현재 위치에서 갈 수 있는 모든 구역이 필승 위치라면 필패 위치로, 그렇지 않다면 필승 위치로 기록합니다. 그리고 오른쪽, 아래, 오른쪽 아래 대각선으로만 움직일 수 있으므로 0 to N, 0 to M이 아닌 N to 0, M to 0로 반복문을 만들어서 메모이제이션하면, 이동할 수 있는 모든 위치가 이미 필승 혹은 필패 위치로 기록됐을 것이므로 올바른 풀이입니다.

 

저는 위의 풀이를 조금 변형하여 N to 0, M to 0로 반복문을 돌면서 현재 위치가 필패 위치라면 현재 위치로 올 수 있는 모든 위치를 필승 위치로 기록했습니다. 아래 코드는 해당 내용을 그대로 옮겨 적은 코드입니다. 글로 이해가 어려웠다면 해당 코드를 참고하시길 바랍니다.

해당 풀이 역시 위에서 말한 이유와 동일하게 올바른 풀이입니다. 천천히 생각해보면 해당 풀이도 유효하다는 것을 떠올릴 수 있을 겁니다.

 

 

주의할 점은 쿼리에서 주어지는 입력이 (x, y)라고 나와있지만 x가 행을 의미하고 y가 열을 의미합니다. 이런 사소한 부분에서 시간을 잡아 먹지 않도록 문제를 잘 읽을 수 있어야 합니다.

 

---

[소스 코드] / Python 3

 

import sys
br = sys.stdin
bw = sys.stdout

N,M,K = map(int, br.readline().split())
arr = [br.readline() for _ in range(N)]
dist = [[False for _ in range(M)] for _ in range(N)]

def isIn(x, y):
    return True if x > -1 and y > -1 else False

def setDist():
    for i in range(N-1, -1, -1):
        for j in range(M-1, -1, -1):
            if arr[i][j] == '#' or dist[i][j] == True: continue
            
            if isIn(j, i-1): dist[i-1][j] = True
            if isIn(j-1, i): dist[i][j-1] = True
            for k in range(1, K+1):
                ni = i-k; nj = j-k
                if not isIn(nj, ni): break
                dist[ni][nj] = True

def main():
    setDist()
    
    Q = int(br.readline())
    while (Q > 0):
        Q -= 1
        x,y = map(int, br.readline().split())
        if dist[x-1][y-1]:
            bw.write("First\n")
        else:
            bw.write("Second\n")
    
    bw.flush()
    bw.close()
    br.close()
        
if __name__ == '__main__':
    main()