[프로그래머스/c++] 사라지는 발판

https://school.programmers.co.kr/learn/courses/30/lessons/92345?language=cpp

프로그래머스

문제 분석

이 문제는 두 플레이어 A와 B가 1x1 크기의 격자로 이루어진 보드 위에서 최적의 전략으로 게임을 진행하는 시뮬레이션 문제이다.

각 플레이어는 발판이 있는 칸에만 이동할 수 있으며, 발판이 사라지는 조건에서 더 이상 이동할 수 없게 되면 패배한다.

게임을 A 가 항상 먼저 시작하며, 양 플레이어는 최선 의 전략을 구사해야 한다.

두 플레이어가 모두 최선의 전략으로 게임을 진행했을 경우 총 이동 횟수를 구해야 한다.

문제 조건 정리

• 각 플레이어는 상하좌우 인접한 발판으로 이동 가능
• 발판이 사라지면 해당 위치로 이동 불가능
  • 해당 플레이어 패배
• A가 항상 먼저 시작

문제 접근법

• 각 플레이어는 자신의 차례에 가능한 모든 방향으로 이동을 시도
• 이동 후 다시 재귀적으로 상대 플레이어의 차례로 넘어간다
• 이동할 수 없는 상태에 도달하면 해당 플레이어가 패배하게 되며, 상대 플레이어가 승리
• 각 상황에서 승리할 수 있는 경우는 승리하는 경로 중 최소 이동 횟수를, 패배하는 경우는 패배하는 경로 중 최대 이동 횟수를 선택

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 방향 벡터 (상하좌우)
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

pair<int, bool> dfs(vector<vector<int>>& board, int ax, int ay, int bx, int by, bool a_turn){

    // A가 서있는 발판이 사라진 경우 (패배)
    if(board[ax][ay] == 0) return {0, false};

    int canWin = false;
    int minMoves = INT_MAX;
    int maxMoves = 0;

    // 4방향으로 이동을 시도
    for(int i = 0; i<4; i++){
        int nax = ax + dx[i];
        int nay = ay + dy[i];

        // 보드를 벗어나거나 발판이 없는 경우 무시
        if(nax < 0 || nay < 0 || nax >= board.size() || nay >= board[0].size() || board[nax][nay] == 0) continue;

        // 발판을 밟고 이동
        board[ax][ay] = 0;
        auto res = dfs(board, bx, by, nax, nay, !a_turn); // 상대방 차례로 이동
        board[ax][ay] = 1; // 복구

        if(!res.second){ // 상대가 패배하는 경우
            canWin = true;
            minMoves = min(minMoves, res.first + 1);
        }else{ // 상대가 승리하는 경우
            maxMoves = max(maxMoves, res.first + 1);
        }
    }

    if(canWin){
        return {minMoves, true}; // 현재 플레이어가 승리할 수 있는 경우
    }else return {maxMoves, false}; // 패배할 수밖에 없는 경우
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    return dfs(board, aloc[0], aloc[1], bloc[0], bloc[1], true).first;
}

int main(){
    vector<vector<int>> t = {{1,1,1},{1,1,1},{1,1,1}};
    solution(t, {1,0},{1,2});
}