[알고리즘] LeetCode - Snakes and Ladders

LeetCode - The World's Leading Online Programming Learning Platform

문제 설명

• 1번부터 시작해서 6까지 잇는 주사위를 던져서 맨끝까지 가는 게임이다.
• 입력으로 정수형 2차원 배열인 board가 주어진다.
• 뱀 또는 사다리가 시작하는 칸에 멈추게 되면 바로 이어진 곳으로 무조건 이동해야 한다.
• 위와 같은 규칙을 통해 이동을 할 때, 끝까지 갈 수 있는 가장 적은 횟수를 반환해야 하고, 만약 갈 수 없다면 -1을 반환해야 한다.

문제 해결

• 2차원 배열을 탐색하기에는 불편하기 때문에 일차원 배열로 변환한다.
• 이후 BFS를 통해 탐색을 진행했다. 
• while문 한번에 한번의 이동이 추가되는 형식으로 구현했다. (예를 들어, 1번의 이동했을 때의 경우를 모두 돌려서 2번째 이동은 어디로 가는지 파악해서 Queue에 삽입)
• 위와 같은 규칙으로 도착할 때까지 반복문을 돌리고, 만약 도착하게 되면 가장 짧은 이동 횟수이기 때문에 바로 리턴한다.
• Queue에 값이 없을 때까지 돌면, 갈 수 있는 경우의 수가 없기 때문에 -1을 리턴한다.

시간 복잡도

• O(NM)

풀이 코드

class Solution {
    static int N, M;
    static int[] newBoard;

    public int snakesAndLadders(int[][] board) {
        N = board.length;
        M = board[0].length;
        newBoard = new int[N * M + 1];

        int idx = 1;
        boolean dir = true;
        for (int y = N - 1; y >= 0; y--) {
            if (dir) {
                for (int x = 0; x < M; x++) {
                    newBoard[idx++] = board[y][x];
                }
            } else {
                for (int x = M - 1; x >= 0; x--) {
                    newBoard[idx++] = board[y][x];
                }
            }
            dir = !dir;
        }

        return bfs();
    }

    static int bfs() {
        int answer = 0;
        Queue<Integer> q = new ArrayDeque<>();
        boolean[] v = new boolean[N * M + 1];

        q.add(newBoard[1] == -1 ? 1 : newBoard[1]);

        while(!q.isEmpty()) {
            int size = q.size();

            for (int i = 0; i < size; i++) {
                int now = q.poll();
                if (v[now]) continue;

                v[now] = true;

                if (now == N * M) return answer;

                for (int j = now + 1; j <= Math.min(now + 6, N * M); j++) {
                    q.add(newBoard[j] == -1 ? j : newBoard[j]);
                }
            }
            answer++;
        }

        return -1;
    }
}

결과

시간	메모리
7 ms	43.2 MB