[프로그래머스] 사라지는 발판 (JAVA 풀이)

 

문제 접근

 

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

프로그래머스

 

 

 

이길 수 있는 경우 최소의 턴으로 이기는 방향으로 가고 이길 수 없는 경우 최대한 오래 버틸 수 있게 하라는게 이해가 안되서 정말 어려웠던 문제였다.

 

이런 경우를 미니맥스 알고리즘이라고 한다는데 이런 구체적인 정보없이도 5x5 board판이므로 모든 경우를 탐색해본다는 생각을 갖고 접근한다면 똑같이 풀 수 있다.

 

문제 풀이

 

상하좌우로 움직일 수 있고 map을 벗어날 수 없으며 발판이 있는 곳으로만 이동할 수 있다는 내용을 보자마자 가장 먼저 방향 벡터와 map을 벗어나는 경우 + 발판이 있는지를 확인해서 해당 공간으로 이동할 수 있는지의 여부를 반환해주는 isRange 함수를 만들어줬다.

 

그 후 dfs를 통해 모든 경우를 탐색하는데 반환값의 경우 int배열을 사용해서 {승리 여부(0이면 승리, 1이면 패배), 턴 수}로 사용했다.

그리고 A부터 이동을 시작해서 A, B, A, B, ... 순서로 번갈아가며 이동을 하기 때문에 이를 하나의 재귀에서 나타내기 위해 opponent와 me 라는 int[]를 통해 A와 B의 현재 위치를 전달해주었다.

 

우선 현재 발판이 사라진다면(같은 위치에 있다 누군가 먼저 이동한다면 발판이 사라지므로) 이동하지못하고 패배하므로 패배를 나타내는 1과 이동하지 못했으므로 턴수 0 을 배열에 담아 {1, 0}을 return 한다.

 

그리고 현재 플레이어가 이기는 경우가 있다면 가장 최소한의 턴으로 승리해야하므로 winTurn변수를 26으로 초기화하였고 (최대 5 * 5 배열이므로 25 이상으로는 턴이 존재할 수 없음) 무조건 패배한다면 가장 오랜 턴으로 버텨야하므로 loseTurn은 0으로 초기화하였다.

 

또한, 현재 플레이어가 어떻게든 이길 수 있는지를 나타내는 canWin과 상하좌우 어디로든 이동할 수 있는지를 나타내는 canMove를 boolean으로 선언해줬다.

 

이제 for문을 통해 방향벡터(상,하,좌,우)로 이동을 하게될텐데 이 때 이동을 하는 순간 위치해있던 발판은 사라지므로 현재 발판인 board[me의 Row값][me의 Col값] = 0을 해주고 상하좌우 이동을 시작했다.

 

=> 만약 이동하려는 곳이 map을 벗어나거나 발판이 없으면 continue를 통해 이동하지 않고 이에 걸리지 않았다면 이동이 가능하므로 canMove를 true로 변경해주었다.

 

그리고 int[] result를 통해 해당 방향으로 이동했을 때 다음 플레이어의 승리 여부와 그 때의 턴 수를 반환받는 재귀의 결과를 받아온다.

(다음 플레이어의 이동을 호출할 때는 플레이어가 바뀌므로 opponent와 me의 위치를 바꿔서 호출해줘야함)

 

=> 이게 이해가 안될 수 있는데 만약 A가 위쪽으로 이동하고 나서 B가 그에 맞춰 이동을하고 또, B가 이동을 했을 때에 맞춰 A가 이동하고  이런식으로 B, A, B, A ... 를 하게 되면 결국 마지막에 누군가 이동을 못하거나 발판이 사라지면 그때 플레이어의 승리, 패배 여부와 턴수를 담아 return 하게 되는데 이를 보고 그 순간 최적의 선택(승리할 수 있으면 최대한 적은턴으로 승리할 수 있는 방향으로 이동, 무조건 패배라면 최대한 많은 턴을 버틸 수 있는 방향으로 이동)을 하게 되며 마지막에는 결국 처음 호출한 A 플레이어 상황에서는 승리, 패배의 여부와 각 결과에 따른 턴 수를 확인할 수 있음

 

일단 for문에 맨 처음 들어갔을 때를 생각해보자

방향벡터에 따라 현재 위치의 위쪽으로 이동할텐데 결국 각 재귀 호출마다 최적의 선택을 해서 얻은 결과물이 {1, 3} 이라고 하자

그럼 {승리 여부, 턴 수} 인데 1이면 패배를 의미한다

 

이때 조심해야할건 승리 여부는 다음 플레이어를 호출했을 때의 결과이므로 내가 위쪽으로 이동했을 때 B의 승리여부가 반환되는 것이다.

즉, {1, 3}은 B가 3턴만에 패배를 한 것을 의미하므로 A 입장에서는 승리하는 결과인 것이다.

 

=> 그래서 result[0] == 1 이라면 A의 승리이고 이 때는 최대한 적은 턴으로 승리를 해야하므로 Math.min을 통해 승리했을 때 가장 적은 턴 수를 담고있는 winTurn 변수를 갱신 해준다

(이 때 추가로 승리가 가능한지를 나타내는 canWin 변수도 true로 갱신해줘야한다)

 

반대로 result[0] == 0 이라면 A입장에서는 B가 승리하는 것이므로 패배를 하게된다.

이 때는 최대한 오래 버티는 턴을 나타내는 loseTurn을 Math.max로 갱신해준다.

 

이렇게 for문을 다 돌아서 상,하,좌,우의 이동에 따른 {승리 여부, 턴 수}를 알아내서 최적의 이동 방향을 찾았으면 탐색을 위해 제거했던 발판을 다시 복구해준다.

 

=> 이를 복구하지 않으면 각 턴을 탐색하면서 발판이 중간중간 사라져있는 상태가 유지되기에 올바른 결과를 찾을 수 없음

 

그럼 for문을 모두 돌았으면 현재 플레이어가 승리를 할 수 있는지(canWin), 이동할 곳이 있는지(canMove), 만약 승리한다면 가장 적은 턴이 몇인지(winTurn), 만약 패배한다면 가장 오래 버틴 턴이 몇인지(loseTurn)이 모두 올바르게 담겨있게된다.

 

만약 canMove가 false라서 이동을 할 수 없다면 해당 플레이어는 패배를 하게 되므로 {1, 0}을 통해 패배를 나타내는 1과 이동을 하지 않았으므로 턴 수 0을 return 해준다

 

만약 움직일 수 있다면 canWin을 살펴봐야한다.

현재 플레이어가 특정 방향으로 이동했을 때 승리하는 경우가 있었다면 무조건 승리를 하는 방향으로 이동을 해야하므로 {0, winTurn + 1}을 담아서 return 해주고 승리하는 경우가 없어서 canWin이 false라면 가장 오래 버티는 방향으로 이동을 해야하므로 {1, loseTurn + 1}을 담아서 return 해준다.

 

=> 참고로 winTurn과 loseTurn은 각각 승리, 패배 시 가장 짧은 턴과 가장 긴 턴이 저장되어 있을 것이고 +1을 해준 이유는 winTurn, loseTurn은 다음 플레이어의 이동을 호출했을 때의 결과 값이므로 현재 플레이어의 이동이 반영되어 있지 않아서 +1을 해준 것이다.

 

쉽게 생각해보면 A가 for문을 돌면서 오른쪽 방향으로 이동했을 때의 상황으로 B를 호출해서 패배, 3이라는 결과를 받았다면 내가 오른쪽으로 이동했을 때 B가 3턴만에 패배를 했다는 의미로 winTurn에 3이 담겨있을 것이다.

 

즉, 내가 오른쪽 방향으로 이동하면 3턴만에 B로부터 승리를 할 수 있다는 의미이므로 현재 오른쪽으로 이동하는 턴을 +1 해줘야 A가 B로부터 승리했을 때의 전체 턴을 구할 수 있다.

 

결국 dfs가 끝나게 되면 solution 함수에 있는 result에는 처음 시작인 A의 승리 여부와 그 때의 최적의 턴 수가 담겨있을 것이고 이 턴 수를 반환해주면 끝난다.

 

전체 코드

 

class Solution {
    
    // 상하좌우 방햑벡터
    int[] dRow = {-1, 1, 0 ,0};
    int[] dCol = {0, 0, -1, 1};
    
    boolean isRange(int row, int col, int[][] board) {
        if(row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
            return false;
        }
        if(board[row][col] == 0) {
            return false;
        }
        return true;
    }
    
    // 반환값: {승리 여부(0: 승리, 1: 패배), 턴 수}
    int[] dfs(int[] me, int[] opponent, int[][] board) {
        
        int meRow = me[0];
        int meCol = me[1];
        
        // 현재 내 발판이 없어지면 패배
        if(board[meRow][meCol] == 0) {
            return new int[] {1, 0}; // {패배, 0턴}
        }
        
        // winTurn은 최소값을 찾아야 하므로 큰 값으로 초기화
        int winTurn = 26; // 최대 5 * 5 이므로 26으로 초기화
        // loseTurn은 최대값을 찾아야 하므로 작은 값으로 초기화
        int loseTurn = 0; 
        boolean canWin = false; // 이길 수 있는지 체크
        boolean canMove = false; // 움직일 수 있는지 체크
        
        board[meRow][meCol] = 0; // 발판 삭제
        
        for(int d = 0; d < 4; d++) {
            int newRow = meRow + dRow[d];
            int newCol = meCol + dCol[d];
            
            if(!isRange(newRow, newCol, board)) continue; 
            
            canMove = true; // 한 번이라도 움직일 수 있음
            
            int[] result = dfs(opponent, new int[] {newRow, newCol}, board);
            
            // result[0] == 1 (상대방 패배) -> 나는 승리
            if(result[0] == 1) { 
                winTurn = Math.min(winTurn, result[1]);
                canWin = true;
            } else { // result[0] == 0 (상대방 승리) -> 나는 패배
                loseTurn = Math.max(loseTurn, result[1]);
            }
        }
        
        board[meRow][meCol] = 1; // 발판 복구
        
        // 움직일 곳이 없어서 졌을 경우
        if(!canMove) {
            return new int[] {1, 0}; // {패배, 0턴}
        }

        if(canWin) {
            return new int[] {0, winTurn + 1}; // 내 턴(+1) 포함 
        } else {
            return new int[] {1, loseTurn + 1}; // 내 턴(+1) 포함
        }
    }
        
    public int solution(int[][] board, int[] aloc, int[] bloc) {
        
        int[] result = dfs(aloc, bloc, board);
        
        return result[1];
    }
}