2022 KAKAO BLIND RECRUITMENT - 사라지는 발판 (JAVA)

❓ 문제 - 2022 KAKAO BLIND RECRUITMENT 사라지는 발판 - JAVA 풀이법

출처 

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

코딩테스트 연습 - 사라지는 발판

 

 

출처 & 참고

(https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/)

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

 

 

(https://velog.io/@weaxerse/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Java-92345%EB%B2%88-%EC%82%AC%EB%9D%BC%EC%A7%80%EB%8A%94-%EB%B0%9C%ED%8C%90)

[프로그래머스/Java] 92345번 사라지는 발판

 

** 위 카카오 해설과 블로그를 참고하여 공부한 풀이입니다. 문제시 삭제하겠습니다..

 

 

📝 문제해결법 

1. board의 행과 열의 크기가 최대 5이고, 플레이어가 2명 그리고 board의 상태가 0 또는 1이므로 완전탐색을 통해 최적 플레이를 통해 두 캐릭터가 움직인 횟수의 합을 구할 수 있다.

 

2. 문제에서 주어진 2가지 상황에 대해 패자와 승자는 정해지며, 패자를 기준으로 백트래킹을 구현하면 하면 된다.

1) 움직일 차례인데 캐릭터의 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우, 해당 차례 플레이어는 패배합니다.
2) 두 캐릭터가 같은 발판 위에 있을 때, 상대 플레이어의 캐릭터가 다른 발판으로 이동하여 자신의 캐릭터가 서있던 발판이 사라지게 되면 패배합니다.

• 문제에서 주어진 이길 수 있는 플레이어는 최대한 빨리 승리를 하고, 질 수 밖에 없는 플레이어는 최대한 오래 버티도록 구현해야 한다.
• A의 턴인지 B의 턴인지만 구분하는 방식으로 재귀 함수를 구현하였다.
• 이 함수에서 한 플레이어가 상, 하, 좌우 4가지 방향 중 이동할 수 잇는 방향으로 이동한 후 게임판의 상황을 바꾼 후 그 상태에서 상대 플레이어에게 넘기는 방식으로 진행된다. 즉. A플레이어 -> B 플레이어 -> A플레이어 -> B플레이어로 진행된다.
• 재귀함수로 구현될 때, 만약 상대 턴으로 넘어간 모든 함수의 결과가 '패배'라면 현재 진행중인 플레이어는 반드시 승리하며, 반대로 상대 턴으로 넘어간 모든 함수의 결과가 '승리'라면 현재 진행중인 플레이어는 반드시 패배할 수 밖에 없다.
• 따라서 이동 횟수에 대한 최댓값 또는 최솟값을 상대방의 결과에 따라 적절하게 변경시키줘야 한다.
• 소스코드 내에서 win_cnt(내가 이기는 플레이어일 때는 빠른 승리를 내야함 -> 플레이턴이 최소), lose_cnt(내가 지는 플레이어일 때는 최대한 느린 패배를 해야함 -> 플레이어턴이 최대)로 둔다.

3. DFS 함수 구현

• a_depth == b_depth 인 경우 A의 플레이어의 움직일 차례이며, a_depth > b_depth 는 B의 플레이어가 움직일 차례이다.
• 현재 플레이어가 있는 자리에서 만약 발판이 없거나 움직일 4방향에 발판이 존재하는 경우가 없는 것이라면 X는 패배한 것이다. 따라서 패배함에 따라 플레이수를 a_depth + b_depth를 반환한다.
• 문제에서 주어진 현재 위치에서 4방향 중에 (움직일 발판의 board 값이 1인경우 && board 범위 내) 로 움직일 수 있을 때 움직이며 만약 현재 플레이어가 아닌 백트래킹을 통해 반환된 여러 경우중에 다른 플레이어가 패배한 경우(Result.win=false)가 존재한다면 현재 나는 이길 수 있는 플레이어가 된다.(win = true)
• 현재 내가 아닌 다른 플레이어의 모든 결과 후에 반환값으로 인해 내가 이길 수 있는 플레이어가 된다면 win_cnt 즉, 빨리 끝낼 수 있는 플레이 수의 최솟값을 갱신하며, 내가 질 수 밖에 없는 플레이어라면 lose_cnt 즉, 최대한 늦게 끝낼 수 있는 플레이의 수의 최대값을 갱신한다.

 

4. 느낀점

• 문제가 주어진 상황과 데이터 범위를 보고 바로 완전 탐색을 떠올렸지만, dfs 내에 조건을 어떤 식으로 구현해야할지 감이 오지 않았다.
• 초반에는 A플레이어가 이긴 플레이어일때의 경우, B플레이어가 이긴 플레이일때의 경우로 고정시켜 놓은 후 완전탐색을 진행해보려고 했지만, 어떤 조건일 때에 이긴 플레이어의 움직임인지, 어떤 조건일 때 진 플레이어의 움직임인지 를 결정하기 어려웠다.
• 여러 고민 끝에 카카오 해설과 다른 사람들의 풀이를 참조하였고, 공통적으로 나타난 것이 이 문제에서 "패배"라는 키워드로 조건을 제시한다는 것이다. 따라서 현재 나 말고, 다음 플레이어가 "패배"한 경우가 존재한다면 내가 자연스럽게 승리하는 플레이어고, 다음 플레이어가 "승리"한 경우라면 내가 자연스럽게 패배하는 플레이어가 되는 접근으로 문제를 해결하면 된다고 깨달았다.
• 카카오 문제가 어려운 알고리즘보다 문제 내에서 힌트를 주는 조건들을 빠르게 파악하여 이것을 구현까지 연결시키는 문제들이 많이 나오는 것 같다. 기출과 비슷한 알고리즘 문제를 풀어보면서 공부해야겠다..! 파이팅 ~~

 

💻 소스코드

// 2022 KAKAO BLIND RECRUITMENT - 사라지는 발판
// 백트래킹

class Solution7_LSH {
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static int n, m;

    
    static class Result {
        boolean win;
        int move_cnt;
        
        public Result(boolean win, int move_cnt){
            this.win = win;
            this.move_cnt = move_cnt;
        }
    }
    
    public int solution(int[][] board, int[] aloc, int[] bloc) {
        n = board.length;
        m = board[0].length;
        return dfs(board, aloc[0], aloc[1], bloc[0], bloc[1], 0, 0).move_cnt;
    }
    
    public static Result dfs(int[][] board, int a_x, int a_y, int b_x, int b_y, int a_depth, int b_depth){
        boolean win = false;
        int win_cnt = 5*5; 
        int lose_cnt = a_depth + b_depth;
        
        // A 움직임
        if(a_depth == b_depth && board[a_x][a_y] == 1){
            for(int d=0;d<4;d++){
                int nx = a_x + dx[d];
                int ny = a_y + dy[d];
                if(!isMovePossible(board, nx, ny)) continue;
                board[a_x][a_y] = 0;
                Result r = dfs(board, nx, ny, b_x, b_y, a_depth+1, b_depth);
                win |= !r.win;
                if(r.win) lose_cnt = Math.max(lose_cnt, r.move_cnt);
                else win_cnt = Math.min(win_cnt, r.move_cnt);
                board[a_x][a_y] = 1;
            }
        }
        // B 움직임
        else if(a_depth > b_depth && board[b_x][b_y] == 1){
            for(int d=0;d<4;d++){
                int nx = b_x + dx[d];
                int ny = b_y + dy[d];
                if(!isMovePossible(board, nx, ny)) continue;
                board[b_x][b_y] = 0;
                Result r = dfs(board, a_x, a_y, nx, ny, a_depth, b_depth+1);
                win |= !r.win;
                if(r.win) lose_cnt = Math.max(lose_cnt, r.move_cnt);
                else win_cnt = Math.min(win_cnt, r.move_cnt);
                board[b_x][b_y] = 1;
            }
        }
        return new Result(win, win ? win_cnt:lose_cnt);
    }
    
    public static boolean isMovePossible(int[][] board, int x, int y){
        if(x < 0 || x >= n || y < 0 || y >= m || board[x][y] == 0) return false;
        return true;
    }
}