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

프로그래머스 사라지는 발판 [2022 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/92345

코딩테스트 연습 - 사라지는 발판

문제 풀이

• 이 문제는 두 플레이어가 번갈아가면서 플레이하여 둘 다 최적의 플레이를 했을 경우 게임이 몇 턴이 진행되는지 알아내는 문제입니다. 
• 최적의 플레이에 대한 정의가 두 가지가 있습니다. 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다.
• 다음으로 승패가 정해지는 두 가지 상황이 있습니다.
  • 자신이 움직일 차례일 때 상하좌우 모두 움직일 수 없는 경우
  • 두 플레이어가 같이 있다가 한 플레이어가 움직여 자신의 발판이 없어진 경우 => 자신의 발판이 없는 경우
• DFS를 사용해 모든 경우의 수를 플레이 해 보면서 내가 이길 경우의 수가 있는 경우 최소 움직임으로, 내가 모든 경우의 수에서 질 경우 최대 움직임으로 플레이하도록 하여 최종 결과를 리턴합니다. 

코드

#include <vector>

using namespace std;

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
int N, M;

bool safe(int y, int x) {
    return y>=0 && x>=0 && y<N && x<M;
}

bool cant_move(vector<vector<int>> &board, int y, int x) {
    for(int d=0; d<4; ++d) {
        int ny = y + dy[d];
        int nx = x + dx[d];
        
        if(safe(ny, nx) && board[ny][nx]) return false;
    }
    return true;
}

pair<bool, int> func(vector<vector<int>> &board, int y1, int x1, int y2, int x2) {
    if(cant_move(board, y1, x1)) return {false, 0}; // 움직일 수 없으면 패배
    
    pair<bool, int> ret = {false, 0};
    if(board[y1][x1]) { // 자신의 발판 있는 경우 => 없으면 바로 패배 리턴
        int minT = 1e9, maxT = 0;
        for(int d=0; d<4; ++d) {
            int ny = y1 + dy[d];
            int nx = x1 + dx[d];
            
            if(!safe(ny, nx) || !board[ny][nx]) continue;
            
            board[y1][x1] = 0;
            auto [win, move] = func(board, y2, x2, ny, nx); // DFS로 모든 경우의 수 플레이
            board[y1][x1] = 1;
            
            if(!win) { // 상대가 질 경우 => 내가 이길 수 있는 경우의 수 : 최소 움직임으로 플레이
                ret.first = true;
                minT = min(minT, move);
            }
            else if(!ret.first) { // 내가 질 경우 : 최대 움직임으로 플레이
                maxT = max(maxT, move);
            }
        }
        
        ret.second = ret.first ? minT+1 : maxT+1;
    }
    
    return ret;
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    N = board.size(), M = board[0].size();
    return func(board, aloc[0], aloc[1], bloc[0], bloc[1]).second;
}

실행 결과