사라지는 발판 - 2022 KAKAO BLIND RECRUITMENT

문제 링크

 

 

상태 전이 개념 + 백트래킹 알고리즘의 적용을 학습하기 좋았던 문제였기에
이렇게 포스트로 기록해둔다.

 

 

이 문제를 읽어보고 나면, 전형적인 게임 이론 문제로 보인다.

 

게임 이론 문제에는 크게 두가지 접근 방식이 있다.

• 게임 로직으로 인해 게임 시작 시 바로 결정되는 승자와 패자를 파악하고, 승자와 패자가 각자의 전략에 맞춰 최적으로 행동하는 방법
• 상태 기계를 설계해, 서로간에 최적의 행동을 직접 수행시켜보고, 행동했을 때 자신이 얻을 수 있는 결과 중 최적을 반환하는 방법

 

이 문제의 경우, 게임 시작 시 바로 결정되는 승자와 패자를 파악하기 어려웠다.

 

따라서 직접 시뮬레이션해보는 두 번째 접근 방식으로 자연스레 손이 가게 되는데,이러면 
-> 내가 이기는 경우, 가장 빨리 끝나는 결과를 알아둔다.
-> 항상 내가 지는 경우, 가장 오래 걸리는 결과를 알아둔다.

문제를 이해해보니 DP가 적용 가능할 가능성이 있긴 한데, 일단 단순한 풀이로 생각해보자.

만약 각 상태별로 각자의 최적을 구한다고 생각하면, 최대 3^25만큼의 시간복잡도가 소모된다.

매번 이동할 수 있는 세 개의 방향이 있다고 가정했고, 최대 25번 이동이 가능하다.

DP를 적용한다고 달라지는건 없나?
같은 상태일 때 재탐색 안해도 되지만, 이는 그만큼의 메모리를 소비한다.

여전히 상태 공간은 2^25 *5^4으로, 상태공간이 너무 크다는 문제가 있다.

 

하지만 이 링크에 설명했듯이, 지수적인 시간복잡도의 경우 비교적 휴리스틱한 접근 방식이 잘 작동할 때가 많다.

Exact 알고리즘과 휴리스틱(근사) 알고리즘의 선택 기준

 

좀 더 자세히 문제를 분석해보면,
- 반드시 외곽(표면적)에만 사람 존재
  - 2^25 * 25

- 각 블록은 부서지는 부분이 연결되어있음
  - 훨씬 많이 줄어들 것 같긴 함

 

따라서 아래와 같이 각자의 최적을 계산하는 함수를 정의하고, 이를 서로 주고받으며 문제를 해결했다.

class Solution {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    public int solution(int[][] board, int[] aloc, int[] bloc) {
        int answer = -1;
        Result result = play(board, 0, aloc, bloc, 0);
        return result.round;
    }
    
    public Result play(int[][] board, int nowPlayer, int[] aloc, int[] bloc, int round){
        
        // 반복문 시작
        Result ret = null;
        for(int k = 0; k<4; k++){
            int[] newAloc = new int[2];
            int[] newBloc = new int[2];
            newAloc[0] = aloc[0];
            newAloc[1] = aloc[1];
            newBloc[0] = bloc[0];
            newBloc[1] = bloc[1];
            if(nowPlayer == 0){
                newAloc[0] += dx[k];
                newAloc[1] += dy[k];
                if(newAloc[0] < 0 || newAloc[0] >= board.length) continue;
                if(newAloc[1] < 0 || newAloc[1] >= board[0].length) continue;
                if(board[newAloc[0]][newAloc[1]] == 0) continue;
                board[aloc[0]][aloc[1]] = 0;
                Result predict = play(board, 1 - nowPlayer, newAloc, newBloc, round+1);
                if(ret == null) ret = predict;
                else if (ret.winner == nowPlayer && predict.winner == nowPlayer && predict.round < ret.round){                    
                    // -> 내가 이기는 경우, 가장 빨리 끝나는 결과를 알아둔다.
                    ret = predict;
                }else if(ret.winner != nowPlayer && predict.winner == nowPlayer){
                    // 내가 이기는 경우가 발생했을 경우, 이를 반환값으로 저장해둔다.
                    ret = predict;
                }else if(ret.winner != nowPlayer && predict.winner != nowPlayer && predict.round > ret.round){
                    // -> 항상 내가 지는 경우, 가장 오래 걸리는 결과를 알아둔다.
                    ret = predict;
                }
                board[aloc[0]][aloc[1]] = 1;
            }else{
                newBloc[0] += dx[k];
                newBloc[1] += dy[k];
                if(newBloc[0] < 0 || newBloc[0] >= board.length) continue;
                if(newBloc[1] < 0 || newBloc[1] >= board[0].length) continue;
                if(board[newBloc[0]][newBloc[1]] == 0) continue;
                board[bloc[0]][bloc[1]] = 0;
                Result predict = play(board, 1 - nowPlayer, newAloc, newBloc, round+1);
                if(ret == null) ret = predict;
                else if (ret.winner == nowPlayer && predict.winner == nowPlayer && predict.round < ret.round){                    
                    // -> 내가 이기는 경우, 가장 빨리 끝나는 결과를 알아둔다.
                    ret = predict;
                }else if(ret.winner != nowPlayer && predict.winner == nowPlayer){
                    // 내가 이기는 경우가 발생했을 경우, 이를 반환값으로 저장해둔다.
                    ret = predict;
                }else if(ret.winner != nowPlayer && predict.winner != nowPlayer && predict.round > ret.round){
                    // -> 항상 내가 지는 경우, 가장 오래 걸리는 결과를 알아둔다.
                    ret = predict;
                }
                board[bloc[0]][bloc[1]] = 1;
            }
            
        }
        // 만약 아무 곳도 방문하지 못했다면, 내 패배로 게임 종료
        if(ret == null){
            return new Result((1 - nowPlayer), round);
        }
        
        // 나랑 같은 위치에 상대가 있었을 경우 내 승리로 게임 종료
        if(aloc[0] == bloc[0] && aloc[1] == bloc[1]){
            if(ret.winner != nowPlayer) ret = new Result(nowPlayer, round+1);
            else if (ret.winner == nowPlayer && ret.round > round+1) ret = new Result(nowPlayer, round+1);
        }
        
        // 나에게 최선의 선택을 반환
        return ret;
    }
}

class Result{
    int winner;
    int round;
    public Result(int winner, int round){
        this.winner = winner;
        this.round = round;
    }
}