[카카오 코딩테스트] 사라진 발판 - javascript

 

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

프로그래머스

 

간만에 알고리즘 관련 글을 써본다.

그만큼 신박했던(?) 문제였기에, 포스팅을 하기로 했다.

 

문제에서 요구하는 알고리즘 자체는 간단하다. board의 크기가 최대 5x5 이기 때문에, 백트래킹과 dfs을 이용해 완전탐색을 수행한다.

하지만, 문제에서 말하는 항상 이길 수 있는 플레이어와 항상 지는 플레이어에 대한 이해를 못햇다...

 

그래서 처음에는 단순히 서로가 플레이를 진행하다 먼저 발판이 사라지는 쪽의 이동거리를 return 하였다.

하지만 이는 당연히 문제가 있었는데, 지는 플레이어가 이기는 플레이어 에게 의도적으로 다가가 일찍 지는 결과가 return 되기 때문이다.

결국 이를 해결 할 아이디어에서 막혀 카카오 해설을 확인해 보고야 문제를 풀 수 있었다. 

 

핵심은 바로 

1. 완전 탐색 수행

2. 완전 탐색 수행 중 이기는 플레이어는 항상 이기기 때문에 다음으로 이동하는 결과중 최소한의 이동거리로 이기는 결과와 승/패 여부를 return 한다.

3. 지는 플레이어는 항상 지기 때문에 최대의 이동거리(최대한 버티는)와 승/패 여부를 return 한다.

 

즉 내가 놓쳤던 부분은,

- 이기는 플레이와 지는 플레이어의 결과가 고정 된다! (문제에서 강조한 항상 이기는 & 지는 플레이어의 의미)

- 이기는 플레이어는 결과들중 최솟값을, 지는 플레이어는 결과들중의 최댓값을 return 한다.  

였다..

 

이를 직관적으로 표현하면,

 

(dfs + 백트래킹 재귀)

return  [승/패여부, 이동거리] -->                                                                                                                  (재귀)

return  [승/패여부, 이동거리] -->         승/패 확인 - 이전이 '패'일 경우 [승,min(이동거리)] return               ------> 

return  [승/패여부, 이동거리] -->.                         - 이전이 '승'일 경우 [패,max(이동거리)] return 

 

 

소스 코드

let h = 0
let w = 0
const dx = [0,-1,0,1]
const dy = [1,0,-1,0]

// 백트래킹 
function dfs (turn, board, aloc, bloc, cnt) {  
    const [ax,ay] = aloc
    const [bx,by] = bloc
    
    let x = 0, y = 0
    // a 턴     
    if(turn === 1) {
        x = ax
        y = ay
    } else { // b 턴
        x = bx
        y = by
    }
    
    // 다음 턴 출발시 내 발판이 비어 있다!!
    if (board[x][y] === 0) {
        return [1,cnt]
    }
    
    
    let winner = []
    let looser = []
    let canMove = false
    for(let i=0; i<4; i++) {
        let nx = x + dx[i]
        let ny = y + dy[i]

        if(nx > -1 && nx< h && ny > -1 && ny < w && board[nx][ny] === 1) {
            canMove = true
            let res = null
            // 현재 발판은 없앤다.
            board[x][y] = 0
            if (turn === 1) {
               res = dfs((-1) * turn, board, [nx,ny], bloc, cnt+ 1)
            } else {
               res = dfs((-1) * turn, board, aloc, [nx,ny], cnt+ 1)    
            }
            // 현재 발판 복귀          
            board[x][y] = 1
            
            let [isWinner] = res
            
            if(isWinner > 0) {
                winner.push(res[1])
            } else {
                looser.push(res[1])
            }
        }
    }
    if(canMove) {
        if(winner.length > 0) {
            return [0, Math.min(...winner)]
        } else {
            return [1, Math.max(...looser)]
        }
    } 
    
    // 이동 불가 -> 상대방 승리
    return [1, cnt]
}

function solution(board, aloc, bloc) {
    h = board.length
    w = board[0].length
    // 첫번째 이동     
    return dfs(1, board, aloc, bloc, 0)[1]
}