프로그래머스 사라지는 발판 자바 풀이

문제 링크

문제 요약

A와 B가 번갈아 발판 위의 캐릭터를 상하좌우로 움직인다
캐릭터가 떠난 발판은 사라진다
이동할 수 없으면 그 차례 플레이어가 패배한다
이길 수 있는 플레이어는 최대한 빨리, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이했을 때 총 이동 횟수를 구한다

문제 풀이

처음에는 각 상태에서 이길 수 있는지 없는지만 boolean으로 판단하는 완전탐색을 생각했다.

하지만 이 방식으로는 정확한 이동 횟수를 구할 수 없다.

문제에서 이기는 쪽은 최대한 빨리 끝내려 하고 지는 쪽은 최대한 오래 버티려 한다고 명시하고 있어서, 승패만 알아서는 부족하다.

실제로 README의 두 번째 예시에서도 같은 승자(B)라도 플레이 방식에 따라 이동 횟수가 6번이 될 수도, 4번이 될 수도 있다고 나온다.

이 문제의 핵심은 각 상태의 결과를 승패가 아니라 "몇 번 만에 게임이 끝나는지"라는 정수로 반환하는 것이다.

dfs(turn)은 지금 턴인 플레이어가 더 이상 움직일 수 없으면 0을 반환하고, 움직일 수 있으면 가능한 모든 이동에 대해 재귀 호출 결과에 1을 더한 값들을 모은다.

결과 값이 홀수면 지금 턴 플레이어가 이기는 경우이므로, 가능한 값 중 최솟값을 택해 최대한 빨리 이기도록 한다
결과 값이 짝수면 지금 턴 플레이어가 지는 경우이므로, 가능한 값 중 최댓값을 택해 최대한 오래 버티도록 한다
이동 전에 발판을 지우고, 재귀 호출이 끝나면 위치와 발판 상태를 원래대로 되돌려서 다른 방향도 시도할 수 있게 한다

최종 코드

java

class Solution {
    public int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}}, board;
    public int[][] loc;
    public int answer = 0, n, m;
    
    // 현재 위치에서 인접한 발판으로 이동 가능한지 확인
    public boolean check(int r, int c){
        if(board[r][c] == 0)
            return false;
        
        for(int d=0;d<4;d++){
            int tr = r+dir[d][0];
            int tc = c+dir[d][1];
            
            if(tr<0 || tr>=n || tc<0 || tc>=m)
                continue;
            
            if(board[tr][tc]!=0)
                return true;
        }
        
        return false;
    }
    
    public int dfs(int turn){
        int r = loc[turn][0];
        int c = loc[turn][1];
        
        if(!check(r,c)){
            return 0;
        }
        
        int win = Integer.MAX_VALUE;
        int lose = 0;
        
        for(int d=0;d<4;d++){
            int tr = r+dir[d][0];
            int tc = c+dir[d][1];
            
            if(tr<0 || tr>=n || tc<0 || tc>=m || board[tr][tc] == 0)
                continue;
            
            loc[turn][0] = tr;
            loc[turn][1] = tc;
            
            board[r][c] = 0; // 떠난 발판은 사라진다
            
            int result = dfs((turn+1)%2) + 1;
            
            loc[turn][0] = r;
            loc[turn][1] = c;
            board[r][c] = 1; // 다른 방향을 시도하기 위해 위치와 발판을 되돌린다
            
            if(result % 2==0){
                lose = Math.max(lose, result); // 지는 경우는 최대한 오래 버티는 쪽을 택한다
            }
            else{
                win = Math.min(win, result); // 이기는 경우는 최대한 빨리 끝내는 쪽을 택한다
            }
        }
        if (win != Integer.MAX_VALUE) {
            return win;
        }
        return lose;
    }
    
    
    public int solution(int[][] board, int[] aloc, int[] bloc) {
        this.board = board;
        loc = new int[2][2];
        for(int i=0;i<2;i++){
            loc[0][i] = aloc[i];
            loc[1][i] = bloc[i];
        }
        n = board.length;
        m = board[0].length;
        
        return dfs(0);
    }
}

사라지는 발판

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기