[ALGORITHM] LEVEL3 2022 KAKAO BLIND RECRUITMENT - 사라지는 발판

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

프로그래머스

과정

1. 만약 움직일 수 없거나 현재 board가 비어있다면 즉시 종료 0을 반환한다.
2. 0 이하가 tmp로 온 경우 상대방의 패배를 의미한다.
   • 상대방의 패배 = 나의 승리 이므로 이동 횟수가 가장 적게 승리해야 하여 minc를 -tmp와 비교하여 갱신해 준다.
3. 0 보다 큰 값이 들어 온 경우 상대방의 승리를 의미한다.
   • 상대방의 승리 = 나의 패배 이므로 이동 횟수가 가장 많게 패배해야 하여 maxc를 tmp와 비교하여 갱신해 준다.
4. 만약 minc가 갱신 되어있다면 내가 그 방향으로만 움직인다면 이기는 최선의 수 이므로 cnt를 minc + 1로 갱신해 준다. minc에는 내가 움직인 횟수가 포함되어 있지 않으므로

코드

#include <string>
#include <vector>

using namespace std;

int mv[4][2]={
    {1,0},
    {-1,0},
    {0,1},
    {0,-1}
};
int N,M;

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

bool canmove(vector<vector<int>>& board, int y, int x){
    for(int m=0;m<4;++m){
        int ny=y+mv[m][0];
        int nx=x+mv[m][1];
        
        if(inside(ny,nx) && board[ny][nx]) return true;
    }
    return false;
}

int calc(vector<vector<int>>& board, int y1, int x1, int y2, int x2){
    if(!canmove(board,y1,x1)) return 0;
    
    int cnt = 0;
    if(board[y1][x1]){
        int minc=987'654'321, maxc = 0;
        
        for(int m=0;m<4;++m){
            int ny = y1+mv[m][0];
            int nx = x1+mv[m][1];
            
            if(!inside(ny,nx) || !board[ny][nx]) continue;
            
            board[y1][x1] = 0;
            int tmp = calc(board,y2,x2,ny,nx);
            board[y1][x1] = 1;
            
            if(tmp <= 0)
                minc = min(minc, -tmp);
            else
                maxc = max(maxc, tmp);
        }
        cnt = minc != 987'654'321 ? minc + 1 : -(maxc + 1);
    }
    return cnt;
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    int answer = 0;
    N = board.size();
    M = board[0].size();
    
    answer = calc(board, aloc[0], aloc[1], bloc[0], bloc[1]);
    
    return answer < 0 ? -answer : answer;
}

참고

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

미니맥스 알고리즘