[Java Script] 909. Snakes and Ladders

1. 문제 개요

문제 링크 : 909. Snakes and Ladders

LeetCode - The World's Leading Online Programming Learning Platform

• 여러 장애물이 있는 길을 통과하여 목표에 도달하는 최소횟수를 찾는 문제

2. 문제 풀이

 

LeetCode 요구 양식으로 코드 구현

/**
 * @param {number[][]} board
 * @return {number}
 */
var snakesAndLadders = function(board) {
    let n = board.length;
    let set = new Set();
    let getPos = (pos) =>{
        let row = Math.floor((pos-1) / n)
        let col = (pos-1) % n
        col = row % 2 == 1 ? n - 1 - col : col;
        row = n - 1 - row;
        return [row,col]
    }
    let q = [[1,0]]
    while(q.length>0){
        [pos,moves] = q.shift();
        for(let i =1; i<7; i++){
            let newPos = i+pos;
            let [r,c] = getPos(newPos);
            if(board[r][c] != -1 ) newPos = board[r][c]
            if(newPos == n*n) return moves+1;
            if(!set.has(newPos)){
                set.add(newPos)
                q.push([newPos,moves+1])
            }
        }
    }
    return -1   
};

 

LeetCode 제출 결과

이렇게 구현에 성공하였습니다.

3. 시간 복잡도 계산

O(nlogn) = O(nlogn)

4. 깃허브

관련 사항은 깃허브에 모두 기재되어 있습니다.