[프로그래머스 / Level3] 사라지는 발판 (Java)

문제 보기

미니맥스 알고리즘이란 상대방의 최고의 수가 나에게 가장 최소의 영향을 끼치게 만드는 것

풀이

• 승자는 최대한 빨리 이기고, 패자는 최대한 오래 버티는 턴 수를 계산하기 위하여 백트래킹 사용
  
  
• 발판이 없어지는 경우 return
• 현재 턴인 플레이어의 갈 수 있는 경우의 수를 계산하여 재귀 호출
• 현재는 턴은 지는 경우인데 새로 계산된 턴이 이기는 경우면 교체
• 모두 지는 경우 최대한 늦게 지는걸 선택
• 모두 이기는 경우 최대한 빨리 이기는걸 선택

class Solution {

    int[][] board;
    int N;
    int M;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int solution(int[][] board, int[] aloc, int[] bloc) {
        this.board = board;
        this.N = board.length;
        this.M = board[0].length;
        return dfs(aloc[0], aloc[1], bloc[0], bloc[1]);
    }

    public int dfs(int plyrX, int plyrY, int opX, int opY) {
        if (board[plyrX][plyrY] == 0) {
            return 0;
        }
        int ret = 0;
        for (int[] dir : dirs) {
            int nextX = plyrX + dir[0];
            int nextY = plyrY + dir[1];
            if (isOOB(nextX, nextY) || board[nextX][nextY] == 0) {
                continue;
            }
            board[plyrX][plyrY] = 0;
            int val = dfs(opX, opY, nextX, nextY) + 1;
            board[plyrX][plyrY] = 1;
            if(ret % 2 == 0 && val % 2 == 1) {
                ret = val;
            } else if(ret % 2 == 0 && val % 2 == 0) {
                ret = ret > val ? ret : val;
            } else if(ret % 2 == 1 && val % 2 == 1) {
                ret = ret < val ? ret : val;
            }
        }
        return ret;
    }

    public boolean isOOB(int x, int y) {
        return x < 0 || x >= N || y < 0 || y >= M;
    }
}