909. Snakes and Ladders

문제

https://leetcode.com/problems/snakes-and-ladders/description/

풀이

class Solution {
    public int snakesAndLadders(int[][] board) {
        Queue<Integer> queue = new LinkedList<>();
        int n = board.length;
        int[] route = new int[n * n +1];
        Arrays.fill(route, -1);
        queue.add(1);
        route[1] = 0;
        int level = 0;

        while(!queue.isEmpty()) {
            int curr = queue.poll();
            if(curr == n * n) {
                return route[curr];
            }
            // 주사위로 갈 수 있는 범위 탐색 
            for(int i = 1; i <= 6 && curr + i <= n * n; i++) {
                int next = curr + i;
                int row = (next - 1) / n;
                int col = (next - 1) % n;
                // 2차원 배열에서의 값 찾기 (주소 변환)
                int special = row % 2 == 0 ? board[n - row - 1][col] : board[n - row - 1][n - col - 1];
                // 뱀이나 사다리로 갈지, 그냥 갈지 결정 - 있다면 무조건 타야함 
                int dest = special > 0 ? special : next;

                if(route[dest] == -1) {
                    route[dest] = route[curr] + 1;
                    queue.add(dest);
                }
            }
        }
        return -1;
    }
}

• 일차원 배열로 바꿔서 탐색 -> 사다리나 뱀이 있는지는 2차원 배열을 이용
• 이동한다면, route[index]에서 index는 주사위를 최소 몇 번 굴려서 도착할 수 있는지를 저장
• 도착한적 있다면 갱신하면 안되므로, route[dest] == -1일때만 queue에 넣어서 탐색