프로그래머스 LV3 사라지는 발판

진짜....... 아이디어가 생각나지도 않고 기준점을 어떻게 잡아야 하는지도 감이 전혀 오지 않았다. 일주일 본다고 달라지진 않을 것 같아서 봐로 답지를 확인했다...

찾아보니 미니맥스 알고리즘, 알파-베타 가지치기 정말 생소한 알고리즘을 활용한 것인데 인공지능 알고리즘였다..

키포인트는 내가 승리하거나 패배하는 것은 결국 상대방이 패배하거나 승리하는 것에 기인된다라는 것이 중점이었던 것 같다.

오랜만에 벽이 느껴져서 작성해본다...

 

 

// 2022 KAKAO BLIND RECRUITMENT - 사라지는 발판
// 백트래킹

class Solution7_LSH {
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static int n, m;

    
    static class Result {
        boolean win;
        int move_cnt;
        
        public Result(boolean win, int move_cnt){
            this.win = win;
            this.move_cnt = move_cnt;
        }
    }
    
    public int solution(int[][] board, int[] aloc, int[] bloc) {
        n = board.length;
        m = board[0].length;
        return dfs(board, aloc[0], aloc[1], bloc[0], bloc[1], 0, 0).move_cnt;
    }
    
    public static Result dfs(int[][] board, int a_x, int a_y, int b_x, int b_y, int a_depth, int b_depth){
        boolean win = false;
        int win_cnt = 5*5; 
        int lose_cnt = a_depth + b_depth;
        
        // A 움직임
        if(a_depth == b_depth && board[a_x][a_y] == 1){
            for(int d=0;d<4;d++){
                int nx = a_x + dx[d];
                int ny = a_y + dy[d];
                if(!isMovePossible(board, nx, ny)) continue;
                board[a_x][a_y] = 0;
                Result r = dfs(board, nx, ny, b_x, b_y, a_depth+1, b_depth);
                win |= !r.win;
                if(r.win) lose_cnt = Math.max(lose_cnt, r.move_cnt);
                else win_cnt = Math.min(win_cnt, r.move_cnt);
                board[a_x][a_y] = 1;
            }
        }
        // B 움직임
        else if(a_depth > b_depth && board[b_x][b_y] == 1){
            for(int d=0;d<4;d++){
                int nx = b_x + dx[d];
                int ny = b_y + dy[d];
                if(!isMovePossible(board, nx, ny)) continue;
                board[b_x][b_y] = 0;
                Result r = dfs(board, a_x, a_y, nx, ny, a_depth, b_depth+1);
                win |= !r.win;
                if(r.win) lose_cnt = Math.max(lose_cnt, r.move_cnt);
                else win_cnt = Math.min(win_cnt, r.move_cnt);
                board[b_x][b_y] = 1;
            }
        }
        return new Result(win, win ? win_cnt:lose_cnt);
    }
    
    public static boolean isMovePossible(int[][] board, int x, int y){
        if(x < 0 || x >= n || y < 0 || y >= m || board[x][y] == 0) return false;
        return true;
    }
}

 

재귀를 활용해서 내가 이길 수 있을 때 무빙 최소값, 내가 진다면 무빙 최대값을 리턴하여 나타내는 것이 포인트였다.
아직까지 재귀를 활용해서 나타내는데 막히는 부분들이 있는 것 같다.. 열공하자...