solution

/**
 * @param {number[][]} board
 * @return {number}
 */
var snakesAndLadders = function(board) {
    let n = board.length;
    let set = new Set();

    function getPosition(pos) {
        // row 당 n개의 원소가 들어있기 때문에 현재 위치를 사용해서 현재 row를 구할 수 있다.
        let row = Math.floor((pos - 1) / n);
      
      	// col도 row와 같은 방법으로 현재 col을 얻을 수 있다.
        let col = (pos - 1) % n;

      	// 그러나, 이 문제는 Boustrophedon style이다.
        // 일반적으로는 위에서 구한 row, col이 현재 위치여야하는데,
        // 구불구불한 모양으로 square의 값이 증가하는 형태이기 때문에 그에 맞게 최적화를 해줘야한다.
        col = row % 2 == 1 ? n - 1 - col : col;
        row = n - 1 - row;

        return [row,col];
    }

    // [현재 square, 현재까지의 이동 횟수]
    let queue = [[1,0]];

    while(queue.length > 0){
        [pos,moves] = queue.shift();

        for(let i = 1; i <= 6; i++){
            let newPos = i + pos;
            let [r,c] = getPosition(newPos);

            // -1이라면 그 square로 이동할 수 있지만, 다른 숫자가 있다면 숫자가 가리키는 square로 이동해야함.
            if(board[r][c] !== -1){
                newPos = board[r][c];  
            }

            // 목적지에 도착하면 이동 횟수를 증가시키고, 연산을 종료한다.
            if(newPos === n * n){
                return moves + 1;
            }

            // 한 번 지나간 square는 다시 지나가지 않도록 Set에서 관리한다.
            if(!set.has(newPos)){
                set.add(newPos);
                queue.push([newPos, moves + 1]);
            }
        }
    }

    return -1; 
};

이 문제는 여러 가지 장치가 있는 길을 어떻게 하면 가장 빨리 지나가서 목표에 도달할 수 있는지를 구하는 BFS 문제이다.
square라고 불리는 각각의 칸들 간에 부모/자식 관계같은 것이 없기 때문에
Tree가 아니라 Graph 문제라고 생각된다.(물론 Tree는 Graph의 일종이다)
가중치가 없기 때문에 BFS를 선택한 것이기도 하다.

6개의 경로를 가질 수 있기 때문에, 가능한 모든 경로를 체크하며 진행한다.
일반적인 nxn 배열이 아니라 구불구불하게 뱀처럼 나열되어있는 형태였기 때문에,
row, col을 그에 맞게 재조정해줄 필요가 있었다.
getPosition()을 통해 문제 상황에 맞춰 조정된 square의 row와 col을 얻는다.
이 때, snake나 ladder를 만나면 반드시 그들을 사용해야하기 때문에 조건 처리를 통해 강제 이동을 시켜준다.
한 번 지나간 square는 다시 지나지 않도록 Set에서 관리해준다. Map을 사용해도 된다.

생각보다 시간 복잡도가 잘 나오지는 않고 있는데, 다른 분들도 거의 동일한 풀이를 가져가고 있기 때문에 신기할 따름이다.

다른 분의 solution

/**
 * @param {number[][]} board
 * @return {number}
 */
var snakesAndLadders = function(board) {
    let n = board.length;
    
    let squares = [];
    
    for (let i = n - 1; i >= 0; i--) {
        let row = board[i];
        
        if ((n - i) % 2 === 0) {
            row.reverse();
        }
        
        squares.push(...row);
    }
        
    let queue = [0];
    let steps = 0;
    let seen = new Set();
    
    while (queue.length) {
        let nextQueue = [];
        steps++;
                
        // 3 options, move to end, move six or move to snake/ladder within six
        for (const square of queue) {
            if (seen.has(square)) {
                continue;
            }
            
            seen.add(square);
            
            // See if we can reach end by moving < 6 squares
            if (n ** 2 - square - 1 <= 6) {
                return steps;
            }
            
            // Try any snakes/ladders in the next 6 moves
            for (i = 1; i < 7; i++) {
                if (squares[square + i] === n ** 2) {
                    // We can reach the final square by snake/ladder
                    return steps;
                }
                
                if (squares[square + i] > -1) {
                    nextQueue.push(squares[square + i] - 1);
                }
            }
            
            // Move ahead as far as we can on non-snake/ladder squares
            for (let i = 6; i > 0; i--) {
                if (squares[square + i] === -1) {
                    nextQueue.push(square + i);
                    break;
                }
            }
        }
        
        queue = nextQueue;
    }
    
    return -1;
};

개인적으로는 예외 처리 부분이 상당히 난해하다고 느끼는 풀이인데,
시간 복잡도가 가장 낮은 풀이이기도 하다.
예외 처리에 대해서는 같은 로직을 사용하고 있다고 생각되는데,
이 분은 초기에 nxn 배열을 만든 뒤에 진행을 하셨다.
앞서 구불구불한 뱀 처럼 배열이 형성되어 있다고 했는데, 이를 일반적인 형태로 변경해서 사용한 것이다!
딱히 square 간 방향이 정해져있던 것은 아니었기 때문에 가능한 방법이라고 생각한다.
다만, 어떻게 배열을 재구성하는 작업을 거쳤음에도 가장 낮은 시간 복잡도를 가졌는지는 의문이다.