프로그래머스 문제 - 사라지는 발판

프로그래머스 사라지는 발판 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

플레이어 A, B가 서로 게임을 하며 양 플레이어 캐릭터의 총 움직임을 예측하려고 한다.
발판에서 다음 발판으로 이동하면 이동 전에 있던 발판이 사라지게 됩니다.
두 플레이어는 같은 발판에 같이 서 있을 수 있습니다.
자신의 차례인데 움직일 수 없거나 상대가 움직여서 자신 아래의 발판이 사라지게 되면 게임이 끝납니다.
게임은 항상 A플레이어 먼저 움직이며 양 플레이어는 최적의 플레이를 하도록 합니다.
최적의 플레이란 이길 수 있는 플레이어는 최대한 빠르게 이기도록 플레이하며 패배할 수 밖에 없는 플레이어는 최대한 오래 버티도록 합니다.
패배할 수 밖에 없는 플레이어는 이길 수 있는 플레이어가 실수하지 않는 이상 패배할 수 밖에 없는 플레이어를 의미합니다.

문제 풀이

게임에서 사용될 법한 문제입니다.
맵은 최대 5X5이기 때문에 완전탐색이 가능하며, 두 플레이어의 최적의 움직임을 중요시하며 문제를 해결해야 합니다.

일단 두 플레이어의 플레이를 계산해보면 총 움직임이 짝수라면 늦게 시작한 B플레이어의 승리이며 홀수라면 A플레이어의 승리라는 것을 알 수 있으며 두 플레이어는 자신이 이긴다는 것을 알게 된다면 최대한 자신에게 유리한 방향으로 이동을 할 것입니다.
이는 플레이어가 진행할 방향으로 dfs를 실행하여 게임이 끝날 때까지의 이동 횟수를 알게 되면 진행할 방향이 플레이어에게 유리한 방향인지 알 수 있습니다.

이를 구현하기 위해 dfs를 통해 자신이 진행할 방향으로 간다면 게임이 끝났을 때의 총 움직임을 알아내줍니다.
현재는 자신이 패배할 수 있지만 진행할 방향으로 움직일 시 자신이 이길 수 있다면 그때의 총 움직임을 저장해줍니다.
만약 자신이 패배할 수 있는 상황이며 진행할 방향으로 가더라도 패배할 수 있는 상황이면 총 움직임이 많은 쪽을 저장해줍니다.
마지막으로 자신이 이길 수 있는 상황이며 진행할 방향도 자신이 이길 수 있는 상황이면 총 움직임이 작은 쪽을 저장해줍니다.

이런 식으로 재귀를 돌리면 마지막에는 플레이어들이 최적의 움직임으로 게임을 끝내는 총 움직임을 알아낼 수 있습니다.

전체 코드

이번 문제는 게임에서나 볼 법한 문제였습니다.
재귀의 작동 방식을 좀 더 깊게 알 수 있어 좋은 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int boardSizeX;
int boardSizeY;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
vector<vector<int>> gameBoard;

int solve(int curX, int curY, int oppX, int oppY)
{
    //만약 보드 위치에 바닥이 없으면 리턴
    if(gameBoard[curX][curY] == 0)
    {
        return 0;
    }
    //반환해줄 값
    int ret = 0;
    for(int i = 0; i < 4; i++)
    {
        int nx = curX+dx[i];
        int ny = curY+dy[i];
        if(0 > nx || nx >= boardSizeX || 0 > ny || ny >= boardSizeY)    continue;
        
        if(gameBoard[nx][ny] == 1)
        {
            gameBoard[curX][curY] = 0;
            //정해진 방향으로 갔을 때의 값을 재귀로 구해줌
            int val = solve(oppX, oppY, nx, ny) + 1;
            gameBoard[curX][curY] = 1; 
            
            if(ret % 2 == 0 && val % 2 == 1)    //현재는 지고 있지만 구해온 값이 이길 수 있을 때
            {
                ret = val;
            }
            else if(ret % 2 == 0 && val % 2 == 0)   //현재는 지고 있고 구해온 값도 지고 있을 때
            {
                ret = max(ret, val);
            }
            else if(ret % 2 == 1 && val % 2 == 1)   //현재는 이기고 있고 구해온 값도 이기고 있을 때
            {
                ret = min(ret, val);
            }
        }
    }
    return ret;
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    int answer = -1;
    boardSizeX = board.size();
    boardSizeY = board[0].size();
    gameBoard = board;

    answer = solve(aloc[0], aloc[1], bloc[0], bloc[1]);
    
    return answer;
}

출처

https://school.programmers.co.kr/learn/courses/30/lessons/92345