(프로그래머스 KAKAO JS)사라지는 발판

https://school.programmers.co.kr/learn/courses/30/lessons/92345?language=javascript 

프로그래머스

 

DFS를 이용해 시뮬레이션을 풀었다.

 

dfs에 전달하는 것은 현재 플레이어의 x, y 좌표, 다음 플레이어의 x, y 좌표다.

우선 return할 변수 result를 선언하여 [false, 0]으로 저장한다.

result는 [진행 여부, 움직인 횟수]를 뜻한다.

 

우선 인자로 받아온 좌표(ax, ay)가 상하좌우로 움직일 수 있는지 판단한다.

만약 4방향 모두 움직일 수 없다면 바로 result를 리턴해주면 된다.

 

이동할 수 있는 위치가 있다면 board[ax][ay]를 확인해서 값이 1이라면 게임을 계속 진행한다.

currentMin과 currentMax를 선언해서 움직인 횟수를 저장할 것이다.

 

for문으로 현재 ax, ay에서 4방향을 확인해 움직일 수 있는 좌표를 구한다.

움직일 수 있는 좌표가 있다면 현재 위치 board[ax][ay] = 0으로 바꾼다.

현재 플레이어가 움직였으니 다음 플레이어가 움직일 수 있도록 인자를 전달해준다.

bx, by, nextAX, nextAY를 전달해서 dfs를 쭉 진행.

해당 dfs가 끝났다면 다시 돌아와 board[ax][ay] = 1로 바꿔준다.

 

결과값으로 받아온 tmp 값이 false라는 것은 다음 플레이어가 더 이상 진행할 수 없다는 뜻이 된다.

그렇다면 result[0] = true로 바꾸고, currentMin값을 tmp[1]과 비교하여 더 작은 값을 저장한다.

그렇지 않고 tmp[0]이 true라면 현재 플레이어는 진행할 수 없으며, currentMax와 tmp[1]을 비교하여 더 큰 값을 저장한다.

 

for문이 끝났다면 result[1]의 값을 갱신해야 한다.

만약 result[0]이 true라면 currentMin + 1을, 아니라면 currentMax + 1을 해주고 리턴하면 된다.

function solution(board, aloc, bloc) {
    const R = board.length;
    const C = board[0].length;
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    
    const checkRange = (x, y) => {
        if(x >= 0 && x < R && y >= 0 && y < C){
            return true;
        }
        
        return false;
    }
    
    const canMove = (x, y) => {
        for(let i = 0; i < 4; i++){
            let nx = x + dx[i];
            let ny = y + dy[i];
            
            if(checkRange(nx, ny) && board[nx][ny]){
                return true;
            }
        }
        
        return false;
    }
    
    const dfs = (ax, ay, bx, by) => {
        const result = [false, 0];
        
        if(!canMove(ax, ay)){
            return result;
        }
        
        if(board[ax][ay]){
            let currentMin = Infinity;
            let currentMax = -Infinity;
            
            for(let i = 0; i < 4; i++){
                const nextAX = ax + dx[i];
                const nextAY = ay + dy[i];
                
                if(!checkRange(nextAX, nextAY) || !board[nextAX][nextAY]){
                    continue;
                }
                
                board[ax][ay] = 0;
                const tmp = dfs(bx, by, nextAX, nextAY);
                board[ax][ay] = 1;
                
                if(!tmp[0]){
                    result[0] = true;
                    currentMin = Math.min(currentMin, tmp[1]);
                } else if(!result[0]){
                    currentMax = Math.max(currentMax, tmp[1]);
                }
            }
            
            result[1] = result[0] ? currentMin + 1 : currentMax + 1;
        }

        return result;
    }
    
    return dfs(aloc[0], aloc[1], bloc[0], bloc[1])[1];
}