[LeetCode] 909. Snakes and Ladders

출처: leetcode.com/problems/snakes-and-ladders/

Snakes and Ladders - LeetCode

문제

N x N board에서, 1에서 N*N까지의 숫자가 보드의 왼쪽 아래에서 시작하여 각 행의 방향을 번갈아가며 적혀있다. 예를 들어, 6 x 6 보드는 다음과 같이 번호가 적혀있다.

보드의 1(보드의 마지막 행에서 첫 번째 열)에서 시작해서 다음의 규칙을 따른다:

• 목적지 S를 <= N*N인 x+1,x+2,x+3,x+4,x+5, 또는 x+6에서 선택한다.
  • 이 선택은 정육면체 주사위의 결과를 시뮬레이션한 것이다; 보드의 크기와 관계없이 6개의 목적지가 있다.
• 만약 S에 뱀 또는 사다리가 있다면, 뱀 또는 사다리의 목적지로 이동해야한다. 아니라면 S로 이동한다.

행 r과 열 c에서 board[r][c] != -1이라면 "뱀 또는 사다리"가 있는 것이다. 뱀 또는 사다리의 목적지는 board[r][c]이다.

 

한번의 움직임당 최대 한번의 뱀 또는 사다리를 탈 수 있음을 주의해라; 뱀 또는 사다리의 목적지에 또다른 뱀 또는 사다리가 존재한다 하더라도 연속해서 움직일 수는 없다.

 

N*N에 도달할 수 있는 최소 움직임 수를 반환하라. 가능하지 않다면 -1을 반환하라.

예제

Input: [
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
At the beginning, you start at square 1 [at row 5, column 0].
You decide to move to square 2, and must take the ladder to square 15.
You then decide to move to square 17 (row 3, column 5), and must take the snake to square 13.
You then decide to move to square 14, and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
It can be shown that you need at least 4 moves to reach the N*N-th square, so the answer is 4.

풀이

문제 풀이의 시작점은 BFS 이다.

 

BFS는 그래프 탐색 알고리즘인데, 문제에 어떻게 적용시킬 수 있을까. 문제에서 주어진 움직임에 대한 규칙을 이용해서 게임판(board)를 다음과 같이 재구성할 수 있다.

• 1번 노드는 2 ~ 7노드와 연결되어 있다고 생각할 수 있고, 2번 노드는 3 ~ 8노드와 연결되어 있다고 생각할 수 있다.
• 이를 전체로 확장시키면 한 노드당 6개의 다른 노드와 연결된 그래프로 만들 수 있다.

게임판이 거대한 그래프로 생각될 수있기 때문에 BFS를 이용할 수 있다. 뱀이나 사다리가 없다고 가정하고 BFS를 이용해서 N*N에 도달하는 최소 스텝을 찾는 코드는 다음과 같다.

var snakesAndLadders = function(board) {
    // 각 노드에 대한 방문 표시를 위한 배열
    // 한번 방문한 노드를 재방문하는 경우를 없애기 위함
    const visited = new Array(board.length+1).fill(false);
    visited[1] = true;

    const N = board.length;
    let queue = [[1, 0]];    // [number of square, number of moves]
    while (queue.length != 0) {
        const cur = queue.shift();

        if (cur[0] == (N*N)) { return cur[1]; }

        for (let i = 1; i <= 6 && cur[0] + i <= N*N; i++) {
            if (!visited[cur[0]+i]) {
                visited[cur[0]+i] = true;
                queue.push([cur[0]+i, cur[1] + 1]);
            }
        }
    }

    return -1;
};

뱀과 사다리를 고려하기 위해서 노드를 좌표로 변경해보자. 행과 열을 다음과 같이 찾을 수 있다.

• 행: (N-1) - ((node-1)/N)
• 열: 노드 번호가 왼쪽에서 오른쪽 방향으로 증가하는 경우와 반대의 경우를 나눠서 생각
  • 왼->오: (node-1) % N
  • 오->왼: (N-1) - ((node-1) % N)

추가적으로 N이 짝수인지 홀수인지에 따라서 왼->오, 오->왼인 행의 위치가 달라진다.

• N이 짝수인 경우: 짝수 행이 오->왼 방향으로 노드 값이 커진다.
• N이 홀수인 경우: 홀수 행이 오->왼 방향으로 노드 값이 커진다.

function getCoordinate(n, cur_square) {
    const row = n - 1 - Math.floor((cur_square -1) / n)
    let col = (cur_square-1) % n;

    if ((n % 2 == 1 && row % 2 == 1) || (n % 2 == 0 && row % 2 == 0)) {
        col = n - 1 - col;
    }

    return [row, col];
}

노드 번호를 좌표로 변경이 가능해졌기 때문에 뱀과 사다리로 인해 이동되어지는 위치를 board[x][y]로 찾을 수 있다. 이를 이용하여 처음의 코드를 수정하면 다음과 같다.

var snakesAndLadders = function(board) {
    const visited = new Array(board.length+1).fill(false);
    visited[1] = true;

    const N = board.length;
    let queue = [[1, 0]];
    while (queue.length != 0) {
        const cur = queue.shift();

        if (cur[0] == (N*N)) { return cur[1]; }

        for (let i = 1; i <= 6 && cur[0] + i <= N*N; i++) {
            const [next_x, next_y] = getCoordinate(N, cur[0] + i);
            const destination = board[next_x][next_y] == -1 ? cur[0] + i : board[next_x][next_y];

            if (!visited[destination]) {
                visited[destination] = true;
                queue.push([destination, cur[1] + 1]);
            }
        }
    }

    return -1;
};

달라진 점은 큐를 업데이트 하기 전에 좌표를 계산하고 계산된 좌표에 접근하여 뱀 또는 사다리를 통한 이동을 체크하는 것이다. 이외 나머지 부분은 동일하다.

 

Github: 909.js

opwe37/Algorithm-Study