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

909. Snakes and Ladders

⭐ 문제

주어진 n x n 정수 행렬 board가 있습니다. 이 행렬의 셀은 아래에서 위로 번갈아가며 번호가 매겨져 있으며, 게임은 보드의 왼쪽 아래에서 시작합니다 (즉, board[n - 1][0]에서 시작합니다).

게임을 시작할 때는 1번 사각형에서 시작합니다. 매 이동마다 현재 위치인 square curr에서 다음 단계를 따릅니다:
1. 범위 [curr + 1, min(curr + 6, n2)] 내의 레이블이 있는 목적지 square next를 선택합니다. 이 선택은 표준 6면 주사위 굴림의 결과를 모방하는 것입니다. 즉, 보드 크기에 관계없이 항상 최대 6개의 목적지가 있습니다.
2. 만약 next에 뱀 또는 사다리가 있다면 해당 뱀 또는 사다리의 목적지로 이동해야 합니다. 그렇지 않으면 next로 이동합니다.
3. 게임은 사각형 n2에 도달할 때 끝납니다.

행 r과 열 c에 있는 보드 사각형에 뱀 또는 사다리가 있는 경우 board[r][c] != -1이 됩니다. 해당 뱀 또는 사다리의 목적지는 board[r][c]입니다. 사각형 1과 n2에는 뱀 또는 사다리가 없습니다.
참고로 이동마다 한 번만 뱀 또는 사다리를 탑니다. 뱀 또는 사다리의 목적지가 다른 뱀 또는 사다리의 시작점인 경우, 다음 뱀 또는 사다리를 따르지 않습니다.
이제 사각형 n2에 도달하는 데 필요한 최소 이동 횟수를 반환합니다. 사각형에 도달하는 것이 불가능한 경우 -1을 반환합니다.

Example 1:

Input: board = [[-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:
In 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 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.
This is the lowest possible number of moves to reach the last square, so return 4.

🤔 접근 방향

문제를 해결하기 위해 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘을 사용합니다. 이 알고리즘은 시작 위치에서부터 목적지까지 가능한 모든 경로를 탐색하며, 최소 이동 횟수를 계산합니다. 뱀과 사다리가 있는 보드는 graph로 생각되며, 각 칸은 node로 표현되고, 뱀과 사다리가 있는 경우 해당 칸 간에 엣지(edge)로 연결됩니다. 게임은 항상 1번 칸에서 시작하며, BFS를 통해 모든 가능한 주사위 굴림 결과를 탐색하고 목적지에 도달하면 이동한 횟수를 반환하며, 도달할 수 없는 경우 -1을 반환합니다.

✍️ 의사 코드

클래스 Solution {
    함수 snakesAndLadders(board: 2차원 정수 배열) -> 정수:
        n = board의 행 길이
        target = n * n

        큐 queue를 생성
        방문 여부를 나타내는 boolean 배열 visited를 생성 (target + 1 크기)

        queue에 1을 추가 # 시작 위치
        visited[1] = 참
        이동 횟수를 나타내는 변수 moves를 0으로 초기화

        while queue가 비어있지 않은 동안:
            큐의 현재 크기를 size에 저장
            size만큼 반복:
                curr = queue에서 원소를 꺼냄
                만약 curr가 목표 위치(target)와 같다면:
                    moves를 반환
                for next = curr + 1부터 Math.min(curr + 6, target)까지 반복:
                    next의 좌표를 얻는 함수를 호출하여 coordinates에 저장
                    row = coordinates[0]
                    col = coordinates[1]

                    목적지를 계산:
                    destination = 만약 board[row][col]가 -1이라면 next, 아니라면 board[row][col]

                    만약 destination이 방문하지 않았다면:
                        destination을 방문했다고 표시
                        queue에 destination을 추가

            moves를 증가

        목적지에 도달할 수 없는 경우 -1을 반환
    end 함수

    함수 getCoordinates(num: 정수, n: 정수) -> 정수 배열:
        num으로부터 좌표 (행과 열)를 계산
        row = (num - 1)를 n으로 나눈 몫
        col = (num - 1)을 n으로 나눈 나머지
        만약 row가 홀수라면:
            col = n - 1 - col
        row = n - 1 - row
        [row, col] 배열 반환
    end 함수
}

✅ 나의 풀이

public class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int target = n * n;

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[target + 1];

        queue.offer(1); // 시작 위치
        visited[1] = true;
        int moves = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                if (curr == target) {
                    return moves;
                }

                for (int next = curr + 1; next <= Math.min(curr + 6, target); next++) {
                    int[] coordinates = getCoordinates(next, n);
                    int row = coordinates[0];
                    int col = coordinates[1];

                    int destination = board[row][col] == -1 ? next : board[row][col];

                    if (!visited[destination]) {
                        visited[destination] = true;
                        queue.offer(destination);
                    }
                }
            }
            moves++;
        }

        return -1; // 목적지에 도달할 수 없는 경우
    }

    // 번호로부터 좌표 (행과 열)를 얻는 함수
    private int[] getCoordinates(int num, int n) {
        int row = (num - 1) / n;
        int col = (num - 1) % n;
        if (row % 2 == 1) {
            col = n - 1 - col;
        }
        row = n - 1 - row;
        return new int[]{row, col};
    }
}

🖥️ 결과

Runtime: 6 ms
Memory Usage: 43.1 MB