[JavaScript] 프로그래머스 - 사라지는 발판

2022 KAKAO BLIND RECRUITMENT

게임 이론 문제입니다.

A와 B가 게임을 합니다.
이기는 사람은 최단 거리로 게임을 승리하려고 하고 지는 사람은 최대한 긴 거리로 게임을 패배하려고 합니다.

게임에서 패배하는 경우
1. 더 이상 움직일 수 없는 경우
2. 발판이 사라진 경우

A와 B는 같은 동작을 하므로 같은 함수로 처리를 해주었습니다.

DFS(현재 사람의 위치, 다음 사람의 위치){
  DFS(다음 사람의 위치, 현재 사람의 바뀐 위치);
}

위와 같은 동작으로 두 사람 모두 같은 함수를 사용할 수 있습니다.

재귀함수를 통해서 완전탐색을 진행합니다.
default는 패배로 승리할 경우의 수가 있다면 승리로 갱신해줍니다. (default = 패배)

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);
}

 

function solution(board, aloc, bloc) {
    let answer = -1;
    const rowSize = board.length;
    const colSize = board[0].length;
    const d = [[0, 1], [1, 0], [-1, 0], [0, -1]];
    let CHK = (y, x) => {
        return y < 0 || x < 0 || y >= rowSize || x >= colSize;
    }
    let DFS = (curLoc, nextLoc) => {      
        let ret = 0;
        if(!board[curLoc[0]][curLoc[1]]) {
            return 0;
        }
        board[curLoc[0]][curLoc[1]] = 0;
        for(let i=0; i<4; ++i) {
            nextY = curLoc[0] + d[i][0];
            nextX = curLoc[1] + d[i][1];     
            if(CHK(nextY, nextX)||!board[nextY][nextX]){
                continue;
            }
            let count = DFS(nextLoc, [nextY, nextX]) + 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);
            }
        }    
        board[curLoc[0]][curLoc[1]] = 1;
        return ret;
    }
    answer = DFS(aloc, bloc); 
       
    return answer;
}