[pro] 프로그래머스 level3 92345 사라지는 발판 (Java) - DFS

[문제]

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

프로그래머스

 

[풀이]

양 플레이어가 최적의 플레이를 해야 한다. 이길 수 있는 플레이어는 최대한 빨리 이겨야 하고, 질수밖에 없는 플레이어는 최대한 오래 버티다 져야 한다.

 

1. 현재 플레이어가 이동했을 때, 발판이 없으면 패배한다.

2. 상하좌우 방향으로 현재 플레이어가 이동 가능하다면 원래 있던 발판을 0으로 바꿔주고, DFS 재귀 호출을 통해 다음 플레이어로 턴을 넘긴다. 

3. 플레이어의 상하좌우가 모두 발판이 없거나 현재 플레이어의 발판이 없으면 DFS 호출이 끝날 것이다. 이동해온 발판을 다시 1로 바꿔준다.

4. 현재 턴에서 지는 경우지만 다음 턴에서 이길 수 있다면 이길 수 있는 케이스로 교체해준다.

5. 지는 플레이어의 경우 최대한 늦게 지도록 플레이해야 한다.

6. 이기는 플레이어의 경우 최대한 빨리 이기도록 플레이해야 한다.

 

* 각 플레이어가 번갈아가면서 이동하다가 한쪽 플레이어가 이동 불가능해지면 승패가 결정날 것이다. 예를 들어, A 플레이어에 대해서 A B A B A 로 이동 후, B가 이동불가능하다면 A의 승리이고, count는 홀수값을 가진다. 반대로 A B A B 로 이동 후, A가 이동불가능하다면 B의 승리, 즉 A의 패배이고 count는 짝수값을 가진다. 따라서 count%2의 값이 0/1 인지에 따라 승패인지를 판단해줄 수 있다. 

 

[코드]

 

class Solution {
    int[] dr = {0, 0, 1, -1};
    int[] dc = {1, -1, 0, 0};
    int n, m;
    public int solution(int[][] board, int[] aloc, int[] bloc) {
        int answer = -1;
        //양 플레이어가 최적의 플레이를 했을 때, 두 캐릭터가 움직인 횟수의 합을 return 
        n = board.length;
        m = board[0].length;
        answer = dfs(aloc[0], aloc[1], bloc[0], bloc[1], board);
        return answer;
    }
    
    public int dfs(int fr, int fc, int sr, int sc, int[][] board){
        if(board[fr][fc]==0){
            return 0; //발판이 없으면 패배
        }
        
        int ret = 0;
        for(int i=0; i<4; i++){
            int nr = fr + dr[i];
            int nc = fc + dc[i];
            
            if(nr<0 || nc<0 || nr>=n || nc>=m) continue;
            if(board[nr][nc]==0) continue;
            
            board[fr][fc] = 0;
            
            int count = dfs(sr, sc, nr, nc, board)+1; //다음 플레이어 턴
            board[fr][fc] = 1;
            
            if(ret%2==0 && count%2==1){
                ret = count; //이길 수 있다면 이기는 케이스로 갱신
            }
            //지는 플레이어인 경우, 최대한 늦게 지도록 플레이
            else if(ret%2==0 && count%2==0){ 
                ret = Math.max(ret, count);
            }
            else if(ret%2==1 && count%2==1){//이기는 플레이어인 경우, 최대한 빨리 승리하도록 플레이
                ret = Math.min(ret, count);
            }
        }
        
        return ret;
    }
    

}