문제

두 플레이어가 있다. 이 게임이 끝날 때까지 양 플레이어의 움직임을 예측하려고 한다.
게임은 다음과 같다.
1. 1x1 크기의 정사각형 격자로 이루어진 총 크기 R * C의 보드에서 이루어진다.
2. 각 플레이어는 서로의 차례에 캐릭터를 상/하/좌/우 중 한곳으로 움직인다.
3. 캐릭터는 발판이 있는곳으로만 이동할 수 있고, 이동한 후에는 원래 있던 발판은 없어진다.
4. 다음 두 상황에서 플레이어는 패배한다.

• 움직일 차례인데 캐릭터 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우
• 두 캐릭터가 같은 발판 위에 있을 때, 상대 플레이어의 캐릭터가 다른 발판으로 이동하며 자신의 캐릭터가 서있던 발판이 사라지게 되는 경우

5. 플레이어 A가 먼저 게임을 시작할 때, 양 플레이어는 최적의 플레이를 한다.

• 최적의 플레이 : 이길 수 있는 플레이는 최대한 빨리 승리, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 하는 플레이

6. 양 플레이어가 최적의 플레이를 했을 때, 두 캐릭터가 움직인 횟수의 합을 반환하는 solution 함수를 만든다.

아이디어

핵심 아이디어

1. 보드의 크기가 최대 5x5 이므로 dfs 완전탐색으로 풀이할 수 있다.
2. 두 플레이어의 움직임을 번갈아 하며 완전탐색한다.
3. '이길 수 있는 플레이어' : 이길 수 있는 루트들이 있다면 그 루트들 최단 루트를 선택한다.
4. '질 수밖에 없는 플레이어' : 단한개의 이기는 루트도 없다면 최대 루트를 선택한다.
5. 기저조건은 둘 중 한명의 플레이어가 패배하는 경우이다.

구현 아이디어

1. 플레이어는 2명, 번갈아 움직이므로 turn이 짝수일때 a턴, 홀수일때 b턴이라 생각하고 구현한다.
2. dfs의 반환값으로 [ 승리 플레이어, 이기기 까지 턴 횟수 ] 를 반환한다.
3. 기저조건
   1. board[현재 위치] == 0 일때, 현재 턴을 가진 플레이어는 패배한다.
   2. 상/하/좌/우 를 모두 살펴봐도 움직일 수 없다면 현재 턴을 가진 플레이어는 패배한다.
4. 한번이라도 이길 수 있다면 최대한 짧은 턴을 반환한다.
5. 한번도 이길 수 없다면 최대한 긴 턴을 반환한다.

코드

dr = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상, 하, 좌, 우
MAX = 9999


def is_valid(r, c, board):
    if 0 <= r < len(board) and 0 <= c < len(board[0]):
        if board[r][c] == 1:
            return True
        return False
    return False


def play_game(board, loc, turn):
    '''
    :param board: 게임 보드
    :param loc: [aloc, bloc] -> [a의 row,col, b의 row, col]
    :param turn: 짝수 - a의 턴 , 홀수 - b의 턴
    :returns : [ winner, turn ] -> 승자/ 이기기 까지의 턴
    '''
    nxt_loc = [[], []]
    min_turn, max_turn = MAX, 0

    # 현재 내 발판이 없을때 패배한다.
    if board[loc[turn % 2][0]][loc[turn % 2][1]] == 0:
        return [(turn + 1) % 2, turn]

    for i in range(4):
        nxt_r = loc[turn % 2][0] + dr[i][0]  # turn % 2 == 0 이면 A
        nxt_c = loc[turn % 2][1] + dr[i][1]  # turn % 2 == 1 이면 B
        nxt_loc[turn % 2] = [nxt_r, nxt_c]
        nxt_loc[(turn + 1) % 2] = loc[(turn + 1) % 2]

        if is_valid(nxt_r, nxt_c, board):
            board[loc[turn % 2][0]][loc[turn % 2][1]] = 0
            ret = play_game(board, nxt_loc, turn + 1)
            board[loc[turn % 2][0]][loc[turn % 2][1]] = 1

            if ret[0] != (turn % 2):  # 내가 현재 방향으로 진행할 때 패배한다면
                max_turn = max(max_turn, ret[1])
            else:  # 내가 현재 방향으로 진행할 때 승리할 수 있다면
                min_turn = min(min_turn, ret[1])

    if max_turn == 0 and min_turn == MAX:  # 초기값을 유지한다는것은 움직이지 않았다를 의미한다.
        # turn % 2 == 0, 현재 A턴, A는 이동하지 못했다. B의 승리
        # turn % 2 == 1, 현재 B턴, B는 이동하지 못했다. A의 승리
        # [ 승자, 턴 ]
        return [(turn + 1) % 2, turn]
    elif min_turn != MAX:  # 한번이라도 이겼으면 최대한 빠르게 끝낸다.
        return [turn % 2, min_turn]
    else:  # 한번도 이긴적 없다면 최대한 길게 턴을 늘린다.
        return [(turn + 1) % 2, max_turn]


def solution(board, aloc, bloc):
    answer = play_game(board, [aloc, bloc], 0)
    return answer[1]