[Java] 909. Snakes and Ladders

문제 파악

 

 

Boustrophedon 스타일의 n*n 보드가 주어진다. ( (n-1,0) 좌표에서 시작한다. )

 

주사위에 따라 최대 6칸을 이동할 수 있다.

 

만약 뱀이나 사다리를 만나면 뱀이나 사다리를 이용해야한다.

 

n^2 칸에 도달했을 때, 게임은 끝난다.

 

보드 값이 -1이 아닌 경우 뱀이나 사다리가 존재한다.

 

뱀이나 사다리인 경우 도착하는 보드 값이 기록되어있다.

 

뱀이나 사다리는 1 또는 n^2 칸에 존재하지 않고 연속으로 이동할 수 없다.

 

n^2에 도달하기 위한 최소 이동 횟수를 반환하고, 도달하지 못하면 -1을 반환한다.

 

 

풀이

1️⃣ 1차원 맵과 bfs 를 이용한 방법

💡 떠오른 Idea

먼저, 보드판 순서가 헷갈려서 이를 1차원 맵으로 바꿔서 해결하면 간단할것이라 생각이 들었다.

따라서, 제일 아래 행부터 시작해서 맵을 1차원으로 변환하는 과정을 거쳐야겠다고 생각했다.

그리고 나서, bfs를 이용해서 사다리에 탄 경우는 사다리 목적지로 이동시킨 위치를 큐에 넣어주고 아닌 경우는 주사위를 굴린 횟수를 더한 값을 큐에 넣어주었다.

그리고 방문했던 칸을 체크해주면서 중복으로 지나가지 않도록 구현하였다.

 

 

class Solution {
    int N;
    int[] map;

    public int snakesAndLadders(int[][] board) {
        N = board.length;
        int end = N * N, result = 0;
        map = new int[end];
        getMap(board);
        boolean[] checked = new boolean[end];

        Queue<int[]> q = new LinkedList<>();

        q.add(new int[]{0, 0});
        checked[0] = true;
        
        while (!q.isEmpty()) {
            int[] info = q.poll();
            int idx = info[0], cnt = info[1];

            for (int i = 1; i <= 6; i++) {
                int next = idx + i;
                if (next >= end - 1) {
                    return cnt + 1;
                } else {
                    if (map[next] != -1) {

                        if (map[next] == end - 1) {
                            return cnt + 1;
                        }
                        if (!checked[map[next]]) {
                            q.offer(new int[]{map[next], cnt + 1});
                            checked[map[next]] = true;
                        }

                    } else {
                        if (!checked[next]) {
                            q.offer(new int[]{next, cnt + 1});
                            checked[next] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }

    private void getMap(int[][] board) {
        boolean flag = true;

        int idx = 0;

        for (int r = N - 1; r >= 0; r--) {
            if (flag) {
                for (int c = 0; c <= N - 1; c++) {
                    map[idx++] = board[r][c] == -1 ? -1 : board[r][c] - 1;
                    flag = false;
                }
            } else {
                for (int c = N - 1; c >= 0; c--) {
                    map[idx++] = board[r][c] == -1 ? -1 : board[r][c] - 1;
                    flag = true;
                }
            }
        }

    }

}

 

결과

 

 

📖 회고

 

문제가 너무 해석하기 어려워서, 한참을 고민했던 것 같다.

 

처음에는 문제를 너무 복잡하게 생각해서 전혀 풀리지 않아 포기할까도 생각했던 문제이다...

 

결국에는 보드판을 이해하기 쉬운 방법으로 변환하고 문제가 요구하는 사항과 bfs를 제대로 구현했더니 해결할 수 있었다.