[LeetCode/Top Interview 150] [Graph BFS (Breadth-First Search)] 909. Snakes and Ladders

문제 링크: https://leetcode.com/problems/snakes-and-ladders/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].
This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
The game ends when you reach the square n2.
A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.
Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -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.
Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1

Constraints:

n == board.length == board[i].length
2 <= n <= 20
board[i][j] is either -1 or in the range [1, n2].
The squares labeled 1 and n2 do not have any ladders or snakes.

전략:

클래식한 보드게임 '뱀과 사다리'를 기반으로 한 문제다. 6면체 주사위를 굴려서 전진하는 만큼, 1턴에 최대 6칸까지 전진 가능하다.
다음 목적지가 뱀이나 사다리라면 해당 뱀/사다리의 목적지로 이동하고, 그 외에는 다음 목적지로 이동한다.
뱀/사다리가 없는 칸은 -1로 표기하며, 뱀/사다리의 목적지는 board[r][c]의 값으로 나타낸다.
한 턴에는 최대 한 번만 뱀 또는 사다리를 이용할 수 있다. 뱀/사다리의 목적지가 다른 뱀/사다리의 시작점이어도 해당 이동은 하지 않는다.
목표는 n^2에 도달하는 것이며, 이때 가장 적은 횟수의 이동 턴을 리턴해 주면 된다.
도달이 불가능한 경우는 -1을 리턴한다.
부스트로페돈 스타일 -> 줄이 바뀔 때마다 좌우 방향이 반대로 바뀜

기본 보드판의 배열을 1차원 배열로 바꾸고, 큐를 통해 BFS로 주사위 이동이 가능한 칸들을 방문한다.
이미 방문한 칸은 visited 배열에 저장하여 무한 반복에 빠지지 않도록 한다.

코드 구현:

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int size=n*n;
        int[] oneDimension = new int[size+1];
        boolean[] visited = new boolean[size+1];
        int cnt = 1;
        // 1차원 배열로 변환
        for (int i=n-1; i>=0; i--) {
            if ((n-i)%2==1) {
                // 홀수행(좌->우)
                for (int j=0;j<n;j++) {
                    oneDimension[cnt++] = board[i][j];
                }
            } else {     
                // 짝수행(우->좌)
                for (int j=n-1;j>=0;j--) {
                    oneDimension[cnt++] = board[i][j];
                }
            }
        }

        Queue<int[]> q = new ArrayDeque<int[]>();
        q.offer(new int[] {1,0});

        while (!q.isEmpty()) {
            int[] before = q.poll();
            int cur = before[0];
            int move_cnt = before[1];            
            if (visited[cur]) {
                continue;
            }
            if (cur == size) {
                return move_cnt;
            }
            visited[cur] = true;

            int dice_move = Math.min(size, cur+6);
            
            for (int i=cur+1; i<=dice_move; i++) {
                if (oneDimension[i] != -1) {                
                    // 뱀 또는 사다리
                    q.offer(new int[] {oneDimension[i], move_cnt+1});
                } else {
                    q.offer(new int[] {i, move_cnt+1});
                }
            }
        }

        return -1;
    }
}
Time: 7 ms (58.1%), Space: 43.2 MB (84.5%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0945-snakes-and-ladders/0945-snakes-and-ladders.java

개선 방안:

이동과 뱀과 사다리를 활용하는 함수를 별도로 만들어서 재귀로 구현한다.

Solutions 탭의 타인 코드:

import java.util.*;
class Solution 
{
    public int snakesAndLadders(int[][] board) 
    {
        int rows = board.length, cols = board[0].length, target = rows * cols, r, c, p;
        boolean[] visited = new boolean[rows * cols + 1]; // cells on board start from 1
        // 1 인덱스에 맞게 1칸 추가
        // queue contains <priority, square> sorted ascending by priority
        // 이동수로 계산한 우선순위 순대로 오름차순 정렬
        // 이동수가 같은 칸들 중에서 보다 결승칸에 가까운 칸들부터 체크한다.
        // prio = #steps * 1000 + (500 - square);
        // 우선도 = #이동수 * 1000 + (500 - 현재 칸)
        // number of steps is critical and adds 1000; 500 is selected as it is higher than the max cell (20*20=400)
        // 
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]); // 우선도 기준 오름차순 정렬
        q.offer(new int[] {0, 1}); // 0 steps to position 1 // 1번 칸에서 이동수 0으로 시작
        visited[1] = true; // 1번칸 방문 체크

        while (!q.isEmpty()) // 다음 칸 남아있으면 방문
        {
            int[] step_pos = q.poll();
            int s = step_pos[0] / 1000 + 1; // s: 이동 횟수
            for (int i = 1; i <= 6; i++) // 주사위 이동
            {
                p = step_pos[1] + i; // 다음 칸
                if (visited[p]) continue; // 방문한 칸이면 스킵
                visited[p] = true; // 방문체크

                r = rows - (p - 1) / cols - 1; // 현재 칸의 행/열 위치 계산
                c = (p - 1) % cols;
                if ((rows - r - 1) % 2 == 1) // 홀수 행에서는 좌우반전
                    c = cols - c - 1; // change direction for odd lines
                int ladder = board[r][c]; // 현재 칸에 적힌 값(-1이면 빈칸, 나머지는 이동칸(뱀/사다리))
                
                if (ladder > 0 && ladder <= target) // 결승점이 아닌 뱀/사다리라면
                    p = ladder; // no update for steps. allow to come here again with a dice
                    // 이동수는 증가하지 않음. 다음에 주사위로 다시 방문 가능
                if (p == target) // 결승 도착
                    return s; // 이동수 리턴
                q.offer(new int[] {s * 1000 + 500 - p, p}); // 다음 칸 이동
            }
        }
        return -1;
    }
}
Time: 4 ms (95.28%), Space: 42.7 MB (98.43%) - LeetHub

회고:

전반적인 로직 자체는 유사하지만, 행 변경을 미리 저장하지 않고 while문 내부에서 처리한 점, 그냥 Queue 대신 PriorityQueue를 사용해 반복 실행시 이동 횟수가 적은 것부터 체크하도록 한 점이 차이가 났는데, 특히 PQ를 활용한 부분이 인상깊었다.
문제에서 제시된 20*20이라는 크기를 잘 활용했다.