문제

플레이어 A와 플레이어 B가 서로 게임을 합니다. 당신은 이 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하려고 합니다.

각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1x1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밞음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서 발판이 있는 칸으로 옮겨야 합니다.

다음과 같은 2가지 상황에서 패자와 승자가 정해지며, 게임이 종료됩니다.

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

게임은 항상 플레이어 A가 먼저 시작합니다. 양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. '이길 수 있는 플레이어'는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, '질 수밖에 없는 플레이어'는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다.

풀이

• board의 크기가 최대 5 * 5 이므로 완전탐색이 가능할 것이다.
• 두 플레이어 모두 최적의 플레이를 하므로 minimax 알고리즘을 사용한다.

minimax 알고리즘을 사용하기 위해 어느 플레이어가 이기고 지는지 알아야한
다. 게임이 끝나는 승리, 패배 조건을 알아야 한다.

• 자신의 차례에서 더이상 움직일 곳이 없는 경우, 패배
• 자신의 차례에서 현재 위치의 발판이 없는 경우, 패배

자신의 차례에서 패배하는 경우만을 종료 조건으로 만들면

• 종료까지 남은 움직임이 홀수, 해당 차례의 플레이어 승리
• 종료까지 남은 움직임이 짝수, 해당 차례의 플레이어 패배

자신이 승리하면 자신이 갈 수 있는 4 방향 중 남은 움직임이 가장 적은 결과를 선택한다.
반대로 자신이 패배하면 남은 움직임이 가장 많은 결과를 선택한다.

남은 움직임을 리턴하는 dfs 함수를 재귀적으로 호출한다.

코드

#include <string>
#include <vector>

using namespace std;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int width;
int height;

bool checkBoundary(int x, int y){
    return (0 <= x && x < height && 0 <= y && y < width);
}

int dfs(vector<int> cur, vector<int> opposite, vector<vector<int>>& board){
    int curx = cur[0];
    int cury = cur[1];
    int max_result = 0;
    int min_result = (1 << 30);
    if (board[curx][cury] == 0){
        return 0; // 겜 끝! 졋음
    }
    
    bool win = false; // for 문을 돌지못하면 움직일 수 없는 거니까 진거임
    for (int d=0; d < 4; d++){
        int nx = curx + dx[d];
        int ny = cury + dy[d];

        if (checkBoundary(nx, ny) && board[nx][ny] == 1){
            board[curx][cury] = 0;
            int step = dfs(opposite, {nx, ny}, board) + 1;
            board[curx][cury] = 1;

            if (step % 2 == 1){ // 미래에서 너 이긴대 겜 빨리 끝내
                win = true;
                min_result = min_result < step ? min_result : step;
            }
            else {
                max_result = max_result < step ? step : max_result;
            }
        }
    }
    return win ? min_result : max_result;
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    int answer = 0;
    height = board.size();
    width = board[0].size();
    
    answer = dfs(aloc, bloc, board);
    return answer;
}

닥터 스트레인지가 타노스와 싸울때 이런식으로 경우의 수를 본 것 같다.