Leetcode 909. Snakes and Ladders

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

LeetCode - The World's Leading Online Programming Learning Platform

https://github.com/fineman999/algorithm_java/issues/14

909. Snakes and Ladders · Issue #14 · fineman999/algorithm_java

---

1. 알고리즘 내용

주어진 n x n 크기의 정수 행렬 board는 보드의 각 칸에 1부터 n^2까지의 번호가 주어진다. 시작점은 보드의 왼쪽 하단, 즉 board[n-1][0]인 1번 칸이다. 각 이동은 다음과 같이 이루어진다.

1. 현재 위치인 칸 curr에서 시작하여, 범위 [curr + 1, min(curr + 6, n^2)] 내의 번호 중 하나를 선택한다. 이 선택은 주사위를 굴린 결과를 모방한 것으로, 보드의 크기와 상관없이 항상 최대 6개의 가능한 목적지가 있다.
2. 선택한 목적지인 next가 뱀이나 사다리가 있는 경우, 해당 뱀이나 사다리의 도착점으로 이동한다. 그렇지 않으면 next로 직진한다.
3. 게임은 n^2번 칸에 도달했을 때 종료된다.
4. 보드의 칸 중에서 board[r][c]가 -1이 아닌 경우, 해당 칸에는 뱀이나 사다리가 있다는 것을 의미하며, 이 뱀이나 사다리의 도착점은 board[r][c]이다. 1번 칸과 n^2번 칸에는 뱀이나 사다리가 없다.
5. 각 이동에서는 한 번의 뱀이나 사다리만 이용할 수 있으며, 만약 해당 뱀이나 사다리의 도착점이 다른 뱀이나 사다리의 시작점이면, 뒤따르는 뱀이나 사다리는 이용하지 않는다.

2. 알고리즘 풀이

public class Solution {
    public int snakesAndLadders(int[][] board) {

        int n = board.length;
        int[] nBoard = setNBoard(board, n);

        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n * n + 1];

        q.add(1);
        visited[1] = true;

        return run(q, nBoard, visited, n);
    }
    
    private int run(Queue<Integer> q, int[] nBoard, boolean[] visited, int n) {
        int steps = 0;
        while(!q.isEmpty()){
            steps++;
            int size = q.size();
            for(int i = 0; i < size; i++) {
                int square = q.poll();
                for(int j = 1; j <= 6; j++) {
                    int next_square = square + j;
                    if (nBoard[next_square] != -1) next_square = nBoard[next_square];
                    if (visited[next_square]) continue;

                    if (next_square == n * n) return steps;
                    visited[next_square] = true;
                    q.offer(next_square);
                }
            }
        }
        return -1;
    }

    private int[] setNBoard(int[][] board, int n) {
        int[] nBoard = new int[n * n + 1];
        int cnt = 1;
        boolean isEven = true;
        for(int i = n - 1; i >= 0; i--) {
            if (isEven) {
                for(int j = 0; j < n; j++) nBoard[cnt++] = board[i][j];
            }else {
                for(int j = n - 1; j >= 0; j--) nBoard[cnt++] = board[i][j];
            }
            isEven = !isEven;
        }

        return nBoard;
    }
}

BFS를 이용하여 문제를 해결하였다.

 

snakesAndLadders 메서드

q는 BFS를 수행할 때 사용하는 큐이다.
visited 배열은 각 칸이 이미 방문되었는지 여부를 나타내며, n * n + 1 크기로 초기화된다.
BFS를 시작하기 위해 1부터 시작 칸을 큐에 추가하고, 해당 칸을 방문했음을 표시한다.

 

setNBoard 메서드

nBoard 배열은 board 배열을 1D 배열로 변환한 것으로, 뱀과 사다리를 고려한 이동 경로를 표시합니다.
2D 보드를 순서대로 탐색하면서 1D 배열에 칸마다 이동해야 하는 다음 칸 또는 뱀과 사다리의 도착지를 기록합니다.

 

run 메서드

visited 배열은 현재까지 방문한 칸을 추적한다.
이 메서드는 BFS를 수행하여 최소 이동 횟수를 계산하고 반환한다.
steps 변수는 이동 횟수를 나타내며, 큐가 비어있을 때까지 반복한다.
각 단계에서 큐에 있는 칸들을 하나씩 처리하면서 주사위를 굴린 결과에 따라 이동한다.
이동할 때, 뱀이나 사다리의 도착지로 이동하거나, 이미 방문한 칸인지 확인한다.
최종 목적지인 n * n에 도달하면 이동 횟수를 반환한다.

3. 결과

단위 테스트 결과

Leetcode 결과