[프로그래머스 - 자바] 사라지는 발판

문제 링크

• 사라지는 발판

풀이

• board의 가로, 세로 길이가 최대 5인 조건을 통해 완전탐색을 사용하면 된다고 판단하였다.
• A턴과 B턴이 번갈아면서 바뀌는 dfs를 사용하였다. 이때 각자의 턴에서 이기는 경우가 없다면 최대 count 값을 반환하였다. 또한, 각자의 턴에서 이기는 경우가 하나라도 존재한다면, 이기는 경우 중 최소 count를 반환하였다.
• 본인의 턴에서 발판이 깨져있다면, 카운팅을 하지 않는 턴이기 때문에 0을 반환하였다.

코드

class Solution {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {-1, 0, 1, 0};
    final int A_NUMBER = 1;
    final int B_NUMBER = -1;
    public int solution(int[][] board, int[] aloc, int[] bloc) {
        Turn turn = dfs(A_NUMBER, board, 
                        new Player(aloc[1], aloc[0]), 
                        new Player(bloc[1], bloc[0]));
        return turn.count;
    }
    
    // 플래이어는 1 또는 -1
    private Turn dfs(int playerNumber, int[][] board, Player A, Player B) {
        // 이기면 min 값을 반환
        // 지면 max 값을 반환
        Player currentPlayer = (playerNumber == A_NUMBER) ? A : B;
        if (board[currentPlayer.y][currentPlayer.x] == 0) {
            return new Turn(0, -playerNumber);
        }
        
        int count = -1;
        boolean canWin = false;
        
        for (int dir = 0; dir < 4; dir++) {
            int nx = currentPlayer.x + dx[dir];
            int ny = currentPlayer.y + dy[dir];
            
            if (nx < 0 || nx >= board[0].length || ny < 0 || ny >= board.length
               || board[ny][nx] != 1) {
                continue;
            }
            
            Turn turn;
            board[currentPlayer.y][currentPlayer.x] = 0;
            if (playerNumber == A_NUMBER) { // A
                turn = dfs(-playerNumber, board, new Player(nx, ny), B);
            } else {
                turn = dfs(-playerNumber, board, A, new Player(nx, ny));
            }
            board[currentPlayer.y][currentPlayer.x] = 1;
            
            if (turn.winner == playerNumber) {
                // currentPlayer가 winner인 Turn의 최소 count가 필요
                if (canWin) {
                    count = Math.min(count, turn.count);
                } else {
                    canWin = true;
                    count = turn.count;
                }
            } else {
                // currentPlayer가 winner가 아닌 Turn의 최대 count가 필요
                if (!canWin) {
                    count = Math.max(count, turn.count);
                }
            }
        }
        
        return new Turn(count + 1, canWin ? playerNumber : -playerNumber);
    }
}

class Player {
    int x;
    int y;
    
    public Player(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Turn {
    int count;
    int winner;
    
    public Turn(int count, int winner) {
        this.count = count;
        this.winner = winner;
    }
}