리트코드 - 909. Snakes and Ladders

리트코드 - 909. Snakes and Ladders

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

 

문제 설명

n x n 크기의 정수 행렬 board가 주어집니다. 이 보드의 각 셀은 1부터 n^2까지의 번호가 부스트로페도(Boustrophedon) 스타일로 배치되어 있습니다. 시작점은 보드의 왼쪽 아래인 board[n - 1][0]에서 시작합니다. 각 행마다 번호가 오름차순인 방향과 내림차순인 방향을 번갈아가며 따릅니다.

 

시작점은 1번 칸입니다. 각 움직임에서 현재 위치인 curr에서 다음을 수행합니다:

• 범위 [curr + 1, min(curr + 6, n^2)] 내에서 레이블이 지정된 목적지 칸 next를 선택합니다. 이 선택은 표준 6면 주사위를 굴린 결과와 유사하게 동작합니다. 즉, 보드 크기에 관계없이 최대 6개의 목적지가 항상 존재합니다.
• 만약 next에 뱀 또는 사다리가 있는 경우, 해당 뱀 또는 사다리의 목적지로 이동해야 합니다. 그렇지 않으면 next 칸으로 이동합니다.
• 게임은 n^2 번 칸에 도달할 때 종료됩니다.

주의: 한 번의 움직임(턴)에서는 최대 하나의 뱀 또는 사다리만을 탈 수 있습니다. 뱀 또는 사다리의 도착지가 다른 뱀 또는 사다리의 시작점일 경우, 이후의 뱀 또는 사다리를 따르지 않습니다.

• 예를 들어, 보드가 [[-1,4],[-1,3]]인 경우, 첫번째 움직임에서 목적지 칸이 2인 경우를 가정해보겠습니다. 당신은 사다리를 따라 3번 칸으로 이동하게 됩니다. 그러나 그 이후의 다음 사다리를 따르지 않습니다.

n^2 번 칸에 도달하기 위해 필요한 최소 움직임 수를 반환하세요. 만약 해당 칸에 도달할 수 없는 경우 -1을 반환하세요.

 

의사코드

함수 snakesAndLadders (board)     map = new HashMap // 게임 보드 저장용     n = board크기     number = 1 // 1번부터     isRightDirection =true      반복문 시작 (board의 제일 아래행부터 위로 순회)         if (isRightDirection)             반복문 시작 (board의 열을 왼쪽부터 순회)                 현재 number와 해당하는 행과 열의 board 값을 map에 추가                 number++             반복문 종료         else             반복문 시작 (board의 열을 오른쪽부터 순회)                 현재 number와 해당하는 행과 열의 board 값을 map에 추가                 number++             반복문 종료         isRightDirection을 전환하여 방향전환     반복문 종료     queue = new LinkedList // BFS 탐색용     visited = new HashSet // 방문한 위치 추적용     count = 0     시작 위치 1을 큐에 추가하고 방문 표시     반복문 시작 (큐가 비어 있지 않으면)         현재 큐의 크기만큼 순회         반복문 시작 (같은 count 가진 값 하나씩 순회)             현재 위치를 큐에서 꺼냄             if (현재위치 == 목표 위치)                 count 리턴                         반복문 시작 (i는 숫자 1부터 6까지 하나씩 순회)                 다음위치 = 현재위치 + i                 if (다음위치 == 목표 위치)                    다음위치를 큐에 추가                                         break             if (다음 위치 < 목표 위치)                 if (다음 위치가 뱀이나 사다리라면)                     이동하는 위치를 다음위치로 추가                                 if (다음위치가 visit한 곳이 아니면)                      visited에 다음 위치 추가                      큐에도 추가             반복문 종료        반복문 종료        count++     반복문 종료     목표 위치에 도달하지 못했다면 -1 리턴

 

풀이코드

class Solution {
    int snakesAndLadders(int[][] board) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = board[0].length;
        int number = 1;
        boolean isRightDirection = true;
        for (int i = n - 1; i >= 0; i--) {
            if (isRightDirection) {
                for (int j = 0; j < n; j++) {
                    map.put(number, board[i][j]);
                    number++;
                }
            } else {
                for (int j = board[0].length - 1; j >= 0; j--) {
                    map.put(number, board[i][j]);
                    number++;
                }
            }
            isRightDirection = !isRightDirection;
        }

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.offer(1);
        int count = 0;
        visited.add(1);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int h = 0; h < size; h++) {
                int current = queue.poll();

                if (current == n * n) {
                    return count;
                }

                for (int i = 1; i < 7; i++) {
                    int nextNumber = current + i;
                    
                    if (nextNumber == n * n) {
                        queue.offer(nextNumber);

                        break;
                    }
                    if (nextNumber < n * n) {
                        if (map.get(nextNumber) != -1) {
                            nextNumber = map.get(nextNumber);
                        }

                        if (!visited.contains(nextNumber)) {
                            visited.add(nextNumber);
                            queue.offer(nextNumber);
                        }
                    }
                }
            }
            count++;
        }
        return -1;
    }
}

코드설명

2차원 배열이 주어졌고 지그재그로 올라가기 때문에 Map을 따로 만들어서 보드판의 숫자를 key로, 이동하는 값을 value로 넣었다.

제일 아래 행부터 왼쪽으로 순회해야 하기 때문에 isRightDirection을 true로 해서 오른쪽으로 순회하고, 이를 flase로 하여 왼쪽부터 순회하는 식으로 해서 map에 넣었다.

 

다음으로 BFS를 위한 queue와 방문한 visited를 HashSet으로 생성했다.

처음에 시작 위치를 queue에 추가하고 방문한 위치로 표시한 다음, queue를 돌린다.

 

위 문제에서 예시로 들면, 1번부터 시작해서 주사위 수(1~6) 만큼 이동할 수 있으므로 BFS를 해보면

이렇게 2부터 7까지 갈수 있을 것이고, 2는 사다리가 있어 15까지 갈 수 있다.

 

그래서 레벨 1에서 갈 수 있는 것은 이렇게 된다. 전부 순회하며 queue에 추가하고, visit에도 추가한다.

poll해서 15를 꺼낸다.

queue에서 15부터 다시 순회하여 visit에 없는 값들만 queue에 추가한다.

그리고, 15가 끝나면 다시 poll하면 3이 나오게 되고 이런식으로 레벨 1을 순차적으로 다 탐색한다.

 

이렇게 하여 BFS탐색을 하다가 어떤 레벨에서 먼저 36에 도달하면 그 값을 리턴하면 된다.(코드에서는 count값)

도달하지 못하면 -1을 리턴하게 된다.

 

예외케이스

도달하지 못하는 예외케이스는 아래와 같은 게 있다.

이 경우 이동할 수 있는 2부터 7까지가 모두 1로 이동하기 때문에 만약 방문한 곳을 표시를 하지 않으면 무한루프에 빠진다.

방문을 체크해야지 visit에 이미 1이 있기 때문에 queue에 아무런 값도 추가 안될 것이고

queue가 비었으므로 반복문을 빠져나오고 -1을 리턴하게 된다.

 

시간복잡도 - O(n^2)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

1. 2차원 배열을 직접적으로 처리하기가 다소 까다롭다.

 

처음에는 아래와 같이 생각함.

for (int i = board.length - 1; i >= 0; i--) {
    if (i % 2 != 0) {
        for (int j = 0; j < board[0].length; j++) {
            map.put(number, board[i][j]);
            number++;
        }
    } else {
        for (int j = board[0].length - 1; j >= 0; j--) {
            map.put(number, board[i][j]);
            number++;
        }
    }
}

 

행(i)의 값을 2로 나누어 나머지를 가지고 왼쪽/오른쪽 순회하는 방법을 생각했는데 이것이 잘못되었음을 깨달았다.

제일 아래칸은 항상 왼쪽에서 오른쪽으로 이동해야 하는데 행의 갯수에 따라 달라지기 때문이다.

예를 들어 3칸짜리 행이면 i는 2일 것이고(인덱스가 0부터 시작이므로),

2 % 2 == 0 이므로 else 분기를 타서 제일 아래는 오른쪽에서 왼쪽으로 이동하게 되어버린다.

 

boolean을 이용해서 계속 바꿔주며 순회하도록 고쳤다.

 

다른코드

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
        // queue contains <priority, square> sorted ascending by priority
        // prio = #steps * 1000 + (500 - square);
        // number of steps is critical and adds 1000; 500 is selected as it is higher than//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
        visited[1] = true;

        while (!q.isEmpty()) 
        {
            int[] step_pos = q.poll();
            int s = step_pos[0] / 1000 + 1;
            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];
                
                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;
    }
}

상당히 재미있는 코드다. 우선 로직은 크게 아래와 같다.

 

1) 우선순위queue를 사용해서 가능성이 높은 걸 먼저 꺼내고 있고,

2) 따로 Map을 쓰지 않고 직접 이동하는 방향을 계산해서 처리하고 있어 훨씬 런타임이 빠르다.

 

이 코드가 재밌는 이유는 queue에 담기는 int배열의 요소 때문이다.

PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);보면 람다식을 이용하여 첫번째 요소에 더 높은 우선순위를 두고 있고 여기에 담기는 int[] 배열은 {s,p}로 되어있는데 s는 이동횟수, p는 이동위치가 된다.

 

s에 재밌는(?) 조작을 해서 우선순위를 만들고 있는데...이해를 위해 먼저 p부터 계산하는 방법을 보겠다.

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

r은 rows(세로 크기) 에서 (p -1) / cols(가로 크기) 한 값을 빼고 또 -1을 빼준다.

rows - 1 은 실제 rows길이와 인덱스간의 차이가 있으므로 1을 빼주는 것이고 (p - 1) / cols 은 줄 개수를 계산하는 값이다.

예를 들어 3*3 의 배열이 있고, 처음위치 1에서 3칸을 이동했다고 하면 p는 초기값이 1이므로 4가 된다.

r = 3 - (4 - 1) / 3 - 1; 하게되면 r = 1 이 나오고 마찬가지로 c = (p - 1) % cols 를 하면 c = 3 % 3 = 0 이 된다.

 

그렇지만 배열에서 두번째 row는 역으로 이동해야 하므로 0이 아니라 2가 되어야 한다.

따라서 맨 아래행을 기준으로 위의 행 부터는 반대로 가는 조건을 걸어주어야 한다.

즉 a부터 b까지 길이를 구하는 공식에 의해, b-a의 값이 홀수인지 판단해주면 된다.

if문에 r = (rows - 1 - r) % 2 == 1 인지 확인하여 true라면 c = cols - 1 - c를 해준다.

 

이렇게 계산한 r과 c를 가지고 board에서 꺼내주면 이동하는 값이 나오는데 이 값이 0보다 크고 끝에 도달하는 값 이하이면 p에 추가해준다. 사다리나 뱀이면 -1이 아닌 값을 가지고 있으므로 이 값을 p에 추가해주는 것이다.

 

이렇게 한 다음 새 int 배열을 만드는데, s에 1000을 곱하고 500에서 -p를 빼준다.(문제조건이 최대 25*25 배열까지이므로 최대크기는 500)

s는 이동횟수로, q에서 꺼낼때 1000으로 나누어 1을 더해줬었다. 따라서 천의 단위가 count의 역할을 한다.

 

우선순위queue 정렬 순에 의해 작은 값이 먼저 poll되므로, 천의 단위가 작을수록(이동횟수가 작을수록), p가 더 많이 갈수록 (500 - p이므로 p가 커질수록 숫자가 작아짐) 먼저 빠져나온다.

 

따라서 일반 queue 보다 훨씬 빠른 경로를 찾을 수 있다.

 

다시 작성

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

        int r;
        int c;
        int p;
        boolean[] visited = new boolean[rows*cols + 1];
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[0] - b[0]);

        q.offer(new int[] {0,1});
        visited[1] = true;

        while(!q.isEmpty()) {
            int[] arr = q.poll();
            int s = arr[0] / 1000 + 1;

            for (int i = 1; i <= 6; i++) {
                p = arr[1] + i;
                if (visited[p]) {
                    continue;
                }
                visited[p] = true;

                r = rows - 1 - (p - 1) / cols;
                c = (p - 1) % cols;
                if ((rows - 1 - r) % 2 == 1) {
                    c = cols - 1 - c;
                }

                int ladder = board[r][c];

                if (ladder > 0 && ladder <= target) {
                    p = ladder;
                }
                if (p == target) {
                    return s;
                }

                q.offer(new int[]{s * 1000 + 500 - p,p});
            }    
        }
        return -1;
    }
}

다른 사람의 코드를 안보고 작성해보는 것도 꽤 재미있는 것 같다.

런타임이 꽤 줄은 것을 볼 수 있다.

 

정리

BFS에 우선순위 큐를 활용하는 방법