[백준 28218] 2023 정올 중등부 1차 격자 게임

문제 출처 : https://www.acmicpc.net/problem/28218

28218번: 격자 게임

이 문제는 2023 정보올림피아드 중등부 1차 2번 문제로 출제 되었습니다. 말의 위치가 정해지면 아래로 한칸 가던가, 오른쪽으로 한칸 가던가, K만큼 대각선으로 움직일 수 있습니다. 두 명이 번갈아 이동해 마지막 칸에 누가 먼저 이동하는지를 대결하는 게임 입니다.

게임 이해하기

두 명 모두 최선을 다하기 때문에 매 번 승리할 수 있는 요소를 확인해야 합니다. 하지만 막상 매 번 승리 요소를 계산한다면 시간초과가 걸릴 수 있습니다. 따라서 우리는 필승의 위치를 먼저 계산하고 역으로 승리를 못하는 위치를 계산한다면 선공이 무조건 이기는 위치, 후공이 무조건 이기는 위치를 알 수 있습니다.

예를 들어 N = 4, M = 5, K = 2인 경우를 생각해 보겠습니다.

이와 같이 지도가 있습니다. 우리는 최종 목표인 G에 누가 먼저 도착하는지를 알고 싶은 것입니다. 그럼 먼저 선공이 무조건 이기는 필승 위치를 표시해 보겠습니다.

1이 있는 위치에서 선공을 한다면 무조건 이길 수 있습니다. 왜냐하면 우리가 갈 수 있는 위치인 아래, 오른쪽 K만큼 대각선에 골(G)이 위치하여 한 턴안에 바로 G로 갈 수 있기 때문 입니다.

다음으로 후공이 절대 가면 안되는 위치를 표시하겠습니다. 선공과 마찬가지로 후공 역시 승리를 위해 노력해야 합니다. 그런 후공이 무조건 이길 수 있는 위치를 찾기는 힘듭니다. 다만 절대 가서는 안되는 위치는 쉽게 찾을 수 있습니다.

바로 2의 위치는 무조건 피해야 하는 자리 입니다. 2의 위치에서는 갈 수 있는 곳이 한 군데이기 때문에 무조건 1로 갈 수밖에 없고, 1로 가게되면 선공이 다음 턴에 G에 도달하여 승리하게 됩니다. 그럼 빨간색 표시된 자리는 왜 안될까요? 빨간색 표시된 자리 역시 1로 갈 수 있어서 가면 안될것 같습니다. 하지만 빨간색 자리에 있다면 1이 있는 곳이 아닌 다른 곳으로 가서 선공의 승리를 가져가지 못하게 할 수 있습니다. 따라서 2번 위치만 가능합니다.

다음으로 선공 차례 입니다. 이제 후공이 2번 위치에 가면 안된다는 것을 알았습니다. 따라서 선공은 후공이 무조건 2번에 갈 수 밖에 없는 위치에 있으면 이길 수 있습니다.

이 그림처럼 2번을 갈 수 있는 위치를 모두 표시하였습니다. 선공이 새로 표시한 1번의 위치에서 시작해 2번 위치로 보낸다면 후공은 2번 위치에서 이전에 표시한 1번으로 갈 수밖에 없고 선공이 이길 수 있습니다.

다음으로 2번을 표시하였습니다. 후공이 절대 가면 안되는 위치 입니다. 이제 또 같은 방법으로 2번에 무조건 갈 수 있는 위치를 표시합니다.

마지막 남은 자리에서는 무조건 1로 가게 되기 때문에 2가 됩니다.

모든 지도에 표시가 끝났습니다. 이제 1의 위치에 먼저 올라간 사람이 무조건 이기게 됩니다.

알고리즘 구현

그럼 위의 내용을 바탕으로 구현하는 방법을 생각해 보겠습니다. 앞서 이해한 게임 내용을 생각해보면 게임을 시작하는 위치가 중요한 것이 아니라 무조건 승리할 수 밖에 없는 위치를 먼저 차지하는 사람이 이기게 됩니다. 즉 거꾸로 승리 위치를 표시하는 방법으로 진행 하겠습니다.

1. 모든 위치가 지는 위치 False로 표시
2. N, M은 골이자, 놓을 수 없는 위치이기 때문에 넘어감
3. 거꾸로 돌면서 False로 갈 수 있는 위치에 True 표시하여 필승 위치 찾아감
4. 시작 위치가 True이면 선공 승리, False 이면 후공 승리

코드 작성

코드를 작성하면서 알고리즘을 구현해 보겠습니다.

입력 받기

mii = lambda : map(int, input().split())
N, M, K = mii()
arr = [[0] * (M+1)]
for _ in range(N):
    arr.append('0' + input())

보드의 크기인 N행과 M열, 대각선으로 얼마나 갈 수 있는지 정하는 K값을 입력 받았습니다. 다음으로 보드를 입력 받습니다. 총 N개의 줄의 입력을 받아 arr 리스트에 추가하였습니다. 이 때 앞에 ‘0’을 추가하여 입력 그대로 행과 열을 사용할 수 있게 하였습니다.

승리 지점 찾기

dp = [[False] * (M+1) for _ in range(N+1)]

for i in range(N, 0, -1):
    for j in range(M, 0, -1):
        if i == N and j == M:
            continue

        if check(i + 1, j):
            dp[i][j] = True
            continue

        if check(i, j + 1):
            dp[i][j] = True
            continue

        for k in range(1, K+1):
            ni = i + k 
            nj = j + k 
            if check(ni, nj):
                dp[i][j] = True
                continue

dp 배열에는 선공이 무조건 이길 수 있는 위치를 표시할 예정입니다. 배열을 만들 때 False 값으로 초기화 합니다. 이 값이 True가 되면 선공이 이기게 됩니다. 다음으로 배열을 탐색합니다. 이 때 도착 지점인 N, M 위치에서부터 확인해야 하기 때문에 배열을 거꾸로 탐색합니다. i가 N, j가 M이 되는 위치는 골인 지점이기 때문에 넘어갑니다. 문제를 잘 읽어보면 이 위치에서는 시작을 할 수 없습니다.

다음으로 아래를 탐색하거나, 오른쪽을 탐색하거나, 대각선으로 K까지 탐색하는 로직을 추가합니다. 이 때 보드를 넘어서거나 막혀있는 길일지도 모르니 check 함수로 확인을 합니다. 확인 결과 승리가 가능하다면 그 지점을 True로 변경한 뒤 다음 탐색으로 넘어갑니다.

check 함수 구현

def check(i, j):
    if 0 < i <= N and 0 < j <= M:
        if arr[i][j] == '.' and dp[i][j] == False:
            return True
    return False

check 함수 입니다. 먼저 가야할 위치인 i, j 가 보드를 벗어나는지 파악합니다. 다음으로 그 위치가 벽(’#’)이 아닌 일반적인 위치(’ . ’) 이면서, 후공이 절대 가면 안되는 False 인지 확인 합니다. 맨 처음 False 를 확인하는 위치는 N, M 의 위치가 될 것이고 그곳이 바로 골(G)의 위치 입니다. 골을 갈 수 있는 위치가 곳 선공이 가야할 True가 되는 것입니다. 그 이후에 만나는 False는 후공이 가면 안되는 위치가 되는 것이고, 선공은 이 위치에 갈 수 있다면 True가 되는 것입니다.

시작 위치 확인하기

Q = int(input())

for _ in range(Q):
    i, j = mii()
    if dp[i][j]:
        print("First")
    else:
        print("Second")

시작 위치를 입력받을 개수는 Q개 입니다. Q개 만큼 입력을 받아 해당 위치 i, j를 확인합니다. 확인 결과 True라면 선공이 무조건 이길 수 있기 때문에 First를 출력하고, False 위치라면 선공이 이길 수 없기 때문에 Second를 출력합니다.

전체 코드

전체 코드를 확인해 보겠습니다.

mii = lambda : map(int, input().split())
N, M, K = mii()
arr = [[0] * (M+1)]
for _ in range(N):
    arr.append('0' + input())

dp = [[False] * (M+1) for _ in range(N+1)]

def check(i, j):
    if 0 < i <= N and 0 < j <= M:
        if arr[i][j] == '.' and dp[i][j] == False:
            return True
    return False

for i in range(N, 0, -1):
    for j in range(M, 0, -1):
        if i == N and j == M:
            continue

        if check(i + 1, j):
            dp[i][j] = True
            continue

        if check(i, j + 1):
            dp[i][j] = True
            continue

        for k in range(1, K+1):
            ni = i + k 
            nj = j + k 
            if check(ni, nj):
                dp[i][j] = True
                continue

Q = int(input())

for _ in range(Q):
    i, j = mii()
    if dp[i][j]:
        print("First")
    else:
        print("Second")