[Leetcode] 909. Snakes and Ladders - JS

https://leetcode.com/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
n x n 보드가 주어지고, 보드 왼쪽 하단에서 시작하여 각 행의 방향을 번갈아 가며 cell을 이동할 때
n^2에 도달하는 최소 주사위 횟수를 반환하라. 만약 불가능하다면 -1을 반환하라.

주사위를 던질 때 현재 위치에서 1~6까지 이동할 수 있고 만약 최대로 이동할 수 있는 위치가 n^2을 넘을 순 없다.
즉, [curr + 1, min(curr + 6, n^2]이 이동가능한 범위이다.

주사위 굴림 당 최대 한 번만 뱀이나 사다리를 가져갈 수 있습니다.
뱀이나 사다리의 목적지가 다른 뱀이나 사다리의 시작인 경우 다음 뱀이나 사다리를 따라가지 않습니다.

제한조건
--------------------
- n == board.length == board[i].length
- 2 <= n <= 20
- board[i][j] -1 또는 1 ~ n^2 사이의 숫자이다.
- 첫번째와 n^2 포인트는 뱀이나 사다리가 아니다.

 

2. 접근 방법

접근방법
--------------------
목적지에 도달하는 최단거리 문제는 BFS 탐색으로 접근한다.
6 x 6 보드를 예시로 했을 때,
1번째 cell에서 시작한다고 했으니 주사위를 던졌을 때, [1+1, 1+6] 사이값이 다음 순서이다.
즉, 1번 cell에서 BFS 탐색을 위해 2,3,4,5,6,7 cell에 도달하는 경우의 수를 queue 자료구조에 넣는다.
이 때, 주사위 굴린 횟수도 같이 전달한다.

다음으로는 각 cell의 숫자를 가지고 board의 좌표를 구해야 한다.
row는 n을 나눈 몫으로 구할 수 있고, col은 n으로 나눈 나머지로 구할 수 있다.
추가로 홀수 row일 때마다 우측 -> 좌측으로 진행하는 것을 고려해야한다.

좌표를 구했는데, 2번 cell의 board 값이 15이므로 1번 cell에서 BFS 탐색을 하게되면
queue에는 [[15,1],[3,1],[4,1],[5,1],[6,1],[7,1]]이 추가된다.
이렇게 진행하면서 cell이 n^2인 36에 도달할 때, 주사위 굴린 횟수를 반환한다.

만약 queue를 모두 순회하여 BFS 탐색이 끝났는데도 반환하지 못하면 -1을 반환한다.

 

 

3. 코드

/**
 * @param {number[][]} board
 * @return {number}
 */
var snakesAndLadders = function(board) {
    const n = board.length;
    
    // 보드의 좌표를 실제 숫자로 변환하는 함수
    function getCoordinates(square) {
        let row = Math.floor((square - 1) / n);
        let col = (square - 1) % n;
        
        // Boustrophedon 스타일 처리
        if (row % 2 === 1) {
            col = n - 1 - col;
        }
        
        return [n - 1 - row, col];
    }
    
    // BFS 탐색
    const queue = [[1, 0]]; // [현재 칸, 이동 횟수]
    const visited = new Set([1]);
    
    while (queue.length) {
        const [square, moves] = queue.shift();
        
        // 최종 칸에 도달했을 때
        if (square === n * n) return moves;
        
        // 다음 가능한 주사위 굴림 (1~6) 탐색
        for (let next = square + 1; next <= Math.min(square + 6, n * n); next++) {
            const [r, c] = getCoordinates(next);
            const destination = board[r][c] === -1 ? next : board[r][c];
            
            // 아직 방문하지 않은 칸이면 큐에 추가
            if (!visited.has(destination)) {
                visited.add(destination);
                queue.push([destination, moves + 1]);
            }
        }
    }
    
    return -1; // 도달할 수 없는 경우
};

 

 

4. 복잡도 분석

- 시간복잡도: O(N^2)

- 공간복잡도: O(N^2)

 

문제가 너무 길어서 이해하기 힘들었는데, 차근차근 번역해서 읽어보면서 이해하려고 노력하니 이해가 됐다.

최단경로 문제는 BFS를 사용하는 것도 이해가 되고, queue 자료구조에 cell 요소와 moves(이동횟수)를 같이 전달하는 방법도 배웠다.

좌표를 구하는 것은 Boustrophedon 유형으로 row가 홀수 일 때, 우측에서 좌측으로 향한다는 것을 고려하는 것도 배웠다.

문제가 길어서 겁먹었지만 의외로 접근할만한 문제였던 것 같다.