[LeetCode 909] Snakes and Ladders - BFS (Python)

문제 요약

1번 칸에서 시작해 주사위를 굴리면서 마지막 칸까지 이동하는 문제다.

한 번에 1~6칸을 이동할 수 있으며, 도착한 칸에 뱀이나 사다리가 있다면 해당 위치로 이동해야 한다.

마지막 칸인 n²에 도착하기까지 필요한 최소 주사위 횟수를 구하면 된다. 도달할 수 없다면 -1을 반환한다.

보드는 일반적인 2차원 배열이지만, 칸 번호는 왼쪽 아래에서 시작해 지그재그로 증가한다.

조건과 입출력

• 2 <= n <= 20
• board는 n × n 크기의 정사각 행렬이다.
• -1은 일반 칸이고, 그 외의 숫자는 뱀이나 사다리의 목적지를 의미한다.
• 한 번에 최대 6칸까지 이동할 수 있다.
• 뱀이나 사다리는 주사위를 한 번 굴릴 때 최대 한 번만 이용한다.

예제 1

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

1 → 2 → 15 → 17 → 13 → 14 → 35 → 36 순서로 이동하면 주사위를 4번 굴려 도착할 수 있다.

예제 2

board = [[-1,-1],[-1,3]]

# Output: 1

풀이 아이디어

처음에는 주사위로 최대 6칸까지 이동할 수 있으니, 가능한 한 멀리 가는 게 유리하다고 생각했다.

다만 중간에 사다리가 있다면 더 적게 이동하는 게 유리할 수도 있고, 뱀을 만나면 뒤로 돌아갈 수도 있다. 그래서 여러 이동 경로를 함께 확인할 수 있는 BFS를 사용했다.

먼저 2차원 배열을 1차원으로 변환했다.

보드 번호가 지그재그로 증가하기 때문에 아래쪽 행부터 읽되, 행마다 읽는 방향을 반대로 바꿔야 한다.

이렇게 변환하면 board_new[0]이 1번 칸, board_new[1]이 2번 칸이 된다. 이후에는 복잡한 행과 열 계산 없이 인덱스만으로 이동할 수 있다.

BFS 큐에는 (현재 위치, 주사위를 굴린 횟수)를 저장했다. 모든 이동은 주사위 한 번으로 이루어지기 때문에 BFS로 탐색하면 최소 횟수를 구할 수 있다.

일반 칸은 가장 멀리 있는 곳만 탐색

여기서 한 가지 최적화를 추가했다.

go = False

for i in range(6, 0, -1):

주사위로 이동할 수 있는 칸을 6칸 앞부터 역순으로 확인한다.

뱀이나 사다리가 있는 칸은 목적지가 달라질 수 있으므로 모두 확인한다.

반면 일반 칸은 방문하지 않은 칸 중 가장 멀리 있는 곳 하나만 큐에 추가했다.

예를 들어 1번 칸에서 4번과 7번 칸 모두 일반 칸이라면, 4번으로 가는 것보다 7번으로 가는 게 유리하다.

4번에서 다음 주사위로 이동할 수 있는 510번 칸 중 57번은 이미 1번에서도 도달할 수 있고, 8~10번은 7번에서 도달할 수 있기 때문이다.

따라서 가까운 일반 칸은 별도로 탐색하지 않아도 된다. 대신 뱀이나 사다리는 반드시 확인해야 한다.

이 역할을 하는 변수가 go다.

제출 코드

from collections import deque

class Solution:
    def snakesAndLadders(self, board: list[list[int]]) -> int:
        n = len(board)

        visited = [False] * n * n
        visited[0] = True

        board_new = []
        for i in range(n):
            if i % 2 == 0:
                for x in board[n-1-i]:
                    board_new.append(x)
            else:
                for j in range(n):
                    board_new.append(board[n-1-i][n-1-j])

        queue = deque()
        queue.append((0,0))
        while queue:
            x,cnt = queue.popleft()

            if x == n*n-1:
                return cnt
            go = False

            for i in range(6,0,-1):
                if x+i < n*n and board_new[x+i] == -1:
                    if not go and not visited[x+i]:
                        queue.append((x+i,cnt+1))
                        go = True

                    visited[x+i] = True

                else:
                    if x+i < n*n and not visited[board_new[x+i]-1]:
                        queue.append((board_new[x+i]-1,cnt+1))
                        visited[board_new[x+i]-1] = True

        return -1

코드에서 신경 쓴 부분

1. 지그재그 보드를 1차원으로 변환

for i in range(n):
    if i % 2 == 0:
        for x in board[n-1-i]:
            board_new.append(x)
    else:
        for j in range(n):
            board_new.append(board[n-1-i][n-1-j])

아래쪽 행부터 읽으면서 홀수 번째 행에서는 방향을 반대로 바꿨다.

2. 뱀과 사다리 처리

board_new[x+i]-1

보드의 칸 번호는 1부터 시작하지만, 배열 인덱스는 0부터 시작한다. 따라서 뱀이나 사다리의 목적지에서 1을 빼서 실제 이동할 인덱스로 사용했다.

목적지에 또 다른 뱀이나 사다리가 있더라도 연속해서 이동하지 않는다.

3. go를 이용한 중복 탐색 줄이기

if not go and not visited[x+i]:
    queue.append((x+i,cnt+1))
    go = True

visited[x+i] = True

같은 위치에서 이동할 수 있는 일반 칸 중 하나만 큐에 넣는다.

큐에 넣지 않은 가까운 일반 칸도 방문 처리하는데, 이는 해당 칸들을 더 멀리 있는 일반 칸으로 대체할 수 있기 때문이다.

일반적인 BFS의 방문 처리와는 조금 다르기 때문에 이 부분은 별도로 생각할 필요가 있었다.

시간 복잡도

보드를 1차원 배열로 변환하는 데 O(n²)이 필요하다.

BFS에서도 최대 n²개의 칸을 확인하고, 각 칸에서는 최대 6개의 이동 후보를 검사한다.

• 시간 복잡도: O(n²)
• 공간 복잡도: O(n²)

visited, board_new, BFS 큐 모두 최대 n² 크기의 공간을 사용한다.

마무리

처음에는 주사위로 최대한 멀리 이동하면서 뱀이나 사다리가 있는 칸만 추가로 확인하면 된다고 생각했다.

이 생각을 바탕으로 BFS를 구현했고, 일반 칸에서는 가장 멀리 있는 칸만 큐에 넣도록 go를 추가했다.

다만 다시 생각해 보니 굳이 이런 최적화를 하지 않아도 됐을 것 같다. 각 칸에서 확인할 수 있는 이동이 최대 6개뿐이어서, 모든 이동 후보를 큐에 넣는 일반적인 BFS로도 충분히 해결할 수 있기 때문이다.

이번에는 기존 방식으로 정답 판정을 받았으니 그대로 남겨두기로 했다.

이번 문제에서 가장 중요했던 부분은 지그재그 형태의 보드를 1차원으로 변환하는 것과, 주사위 이동 횟수가 최소가 되도록 BFS를 사용하는 것이었다.

출처

LeetCode 909. Snakes and Ladders