[JS] 사라지는 발판

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

프로그래머스

 

 

 

문제의 조건 케이스가 5*5 케이스이고 생각해야 할 부분이 많아서 완전탐색을 이용해야 한다고 생각을 했다.

 

 

따라서 처음에 완전탐색으로 모든 게임의 경우의 수를 구하는것까지는 성공했고 테스트 케이스들의 시간초과 또한 나지 않는 것을 확인하였다.

 

그런데 문제가 있었다. 

 

어떻게 정답을 이끌어내지?!
ㅋㅋㅋㅋㅋ

최대값을 정답으로 하자니 최선의 수가 아니게 되고 최소값을 정답으로 해도 최선의 수가 아니게 된다.

 

혼자 고민하다가 이끌어낸 결론은

 

이기는 플레이어 => 최소의 경우의 수로 가야함

지는 플레이어 => 최대의 경우의 수로 가야함

 

아무리 생각해도 내 지식으로는 해결할 수 없을 거 같아 인터넷을 조금 뒤졌더니

 

MINMAX TREE라는것이 있다라는것을 발견했다.

 

 

MINMAX TREE

 

 

알아보니 게임 인공지능 개발에 많이 사용되는 알고리즘 기법이라고 한다. (오목,바둑 등 AI개발에 많이 사용된다고 함)

 

턴제 게임에서 사용할 수 있는 알고리즘으로 모든 경우의 수를 파악한 이후 최선의 선택들을 가져가는 것이다.

 

 

중요한건 내가 최선의 수를 두었을때 이기는지 지는지 알수가 없다.

 

이기는 플레이어 -> 가장 빠르게 게임을 끝내야함

지는 플레이어 -> 최대한 뻐팅겨야함

 

 

 

내가 게임을 이기는지 지는지 알 수 있는 방법은 게임의 끝이다. 즉 모든 경우의 수에서 게임의 승패가 나왔을때부터 거꾸로 돌아가며 (백트래킹) 내가 이긴다면 최소의 수를, 진다면 최대의 수를 계산하면 된다.

 

하지만 게임은 2명이서 하므로 이를 번갈아 가며 최대,최소를 번갈아가며 계산하게 해주면 된다.

 

 

 

 

필자가 해당 문제를 해결한 방법은 아래와 같다.

 

 

이 재귀함수의 역할은 curPR,curPC 앞에 나오는 두 인자를 현재 플레이어라고 생각할때 이기면 최소의 수를, 지면 최대의 수를 계산하여

[승패여부 , 턴의 수] 를 반환해주는 역할을 한다.

 

사실 문제가 재귀함수로 끝나서 코드의 주석을 따라가며 이해하는 것이 더 이해하기 편할 것 같다!

 

 

function solution(board, [aR,aC], [bR,bC]) {
    
    
    const dr = [1,0,-1,0]
    const dc = [0,1,0,-1]
    
    const rLen = board.length
    const cLen = board[0].length
    
    //4방향으로 갈 수 없는지 확인
    const isFinish = (r,c) => {
        for (let k = 0 ; k < 4 ; k++){
            const nR = r + dr[k]
            const nC = c + dc[k]
            if(0<= nR && nR < rLen && 0<= nC && nC < cLen && board[nR][nC]) return false
        }
        return true
    }
    
    // return : [승패여부,움직인 횟수]
    const dfs = (curPR,curPC,othPR,othPC) => {
        // 게임이 끝나는지 확인
        if (isFinish(curPR,curPC)) return [false,0]
        if(curPR===othPR && curPC === othPC) return [true,1]
        // 내가 못움직이면 => 패배할수밖에 없고 다음턴이 없음
        // 내가 움직이면 => 승리할 수 있으며 다음턴 1턴을 진행해야함
        
        
        let canWin = false
        let maxCnt = 0
        let minCnt = Infinity
        
        // 턴을 진행
        for (let k = 0 ; k < 4 ; k++){
            const [nR,nC] = [curPR + dr[k] , curPC + dc[k]]
            if (!(0<= nR && nR < rLen && 0<= nC && nC < cLen && board[nR][nC])) continue
            
            //내가 움직이면서 발판이 사라짐
            board[curPR][curPC] = 0
            //다음턴은 상대의 턴이므로 상대를 현재플레이어로 설정
            const [isOtherWin,cnt] = dfs(othPR,othPC,nR,nC)
            //내 다음 경우의수를 위해서 상대가 움직인 경우를 복구
            board[othPR][othPC] = 1
            
            // 내가 이길 수 있는경우에는 최소 경우의 수를 담는다
            if(!isOtherWin) {
                canWin = true
                minCnt = Math.min(minCnt,cnt)
            }
            // 상대가 이길 수 있는 경우에는 최대 경우의 수를 담는다
            else maxCnt = Math.max(maxCnt,cnt)
        }
        
        return canWin ? [true,minCnt+1] : [false,maxCnt+1]
        
    }
    
    return dfs(aR,aC,bR,bC)[1]
}