Rat in a Maze

Q: Rat in a Maze의 시간 복잡도는 얼마인가요?

첫 번째 이동 후에는 경로가 각 칸에서 최대 세 가지 선택지를 가지며, 최대 n² 개의 칸을 방문하므로, 부분 경로는 O(3^(n²)) 개이고 각 경로를 기록하는 데 O(n²) 의 비용이 듭니다. 벽과 이미 방문한 칸은 이 수를 크게 줄여 줍니다.

Q: 쥐가 오른쪽과 아래쪽으로만 이동할 수 있다면 어떨까요?

그러면 어떤 경로도 셀을 다시 방문할 수 없으므로 방문 표시가 필요하지 않고, 모든 경로는 정확히 2n-2 번 이동합니다. 경로 수 세기는 동적 프로그래밍으로 바뀝니다. 한 셀에 도달하는 방법의 수는 그 위쪽의 열린 셀에 도달하는 방법의 수와 왼쪽의 열린 셀에 도달하는 방법의 수를 더한 것입니다.

보통백트래킹

+10

쥐 한 마리가 n × n 크기의 maze에서 왼쪽 위 칸에서 시작합니다. 1은 열린 칸이고 0은 벽이며, 쥐는 오른쪽 아래 칸에 도달해야 합니다. 한 번 움직일 때 열린 칸으로 한 칸 아래(D), 왼쪽(L), 오른쪽(R) 또는 위쪽(U)으로 이동합니다. 경로에서는 같은 칸을 두 번 방문하지 않으며 출구에서 끝납니다.

모든 경로를 이동 방향을 나타내는 문자열로 반환하세요. 문자열은 알파벳순으로 정렬하고, 경로가 없으면 빈 배열을 반환하세요.

함수

findPaths(maze: integer-2d-array) → string-array

mazeinteger-2d-array: 열린 칸은 1, 벽은 0으로 표시하는 n × n 격자
반환값string-array: 왼쪽 위에서 오른쪽 아래까지의 모든 경로를 이동 방향 문자열로 나타내고, 알파벳순으로

제약 조건

2 ≤ n ≤ 5
maze[i][j]는 0 또는 1입니다.
모든 테스트 미로에는 경로가 최대 2,000개 있습니다. 5 × 5 열린 미로에는 경로가 8,512개 있으므로 테스트에 포함되지 않습니다.

예제

입력: maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
출력: ["RDDRDR", "RDRDDR"]
설명: 처음에는 오른쪽 셀만 열려 있고, 거기서도 아래쪽 셀만 열려 있으므로 두 경로 모두 RD로 시작합니다. 세 번째 이동인 D가 R보다 먼저 오기 때문에 RDDRDR이 먼저 정렬됩니다.

후속 질문

네 가지 이동이 모두 허용될 때, 경로를 하나씩 나열하지 않고 경로의 수를 셀 수 있을까요? 경로의 수가 감당하기 어려워지기 전에 n은 얼마나 커질 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

모든 경로를 빠짐없이, 중복이나 누락 없이 나열해야 합니다. 백트래킹을 사용하면 됩니다. 한 번에 한 수씩 경로를 확장하고, 경로가 지나가는 칸을 막은 다음, 해당 칸에서 되돌아 나올 때마다 막힌 칸을 해제합니다. 이동을 알파벳순으로 시도하면 경로가 정렬된 순서로 나옵니다.

모든 경로를 너비 우선으로 확장한 다음 정렬합니다

핵심 아이디어

각각 현재 칸, 방문한 칸, 이동 경로를 담은 부분 경로를 큐에 보관합니다. 하나를 꺼내 열린 미방문 칸으로 한 번 이동해 확장한 경로를 모두 다시 넣거나, 출구에 도달하면 저장합니다. 모든 경로는 정확히 한 번씩 찾아집니다. 칸이 최대 25개이므로 방문한 칸 집합은 정수 하나에 들어갑니다. 비트 r * n + c는 칸 (r, c)을 나타냅니다.

큐에서는 경로가 짧은 순서대로 나오지만, 정렬된 순서는 아닙니다. 열린 5 × 5 미로에서는 16번 이동하는 DDDDRRRULLURRRDD가 8번 이동하는 DDDRDRRR보다 먼저 정렬됩니다. 따라서 마지막에 정렬해야 하며, 큐에는 부분 경로의 전체 계층이 메모리에 담깁니다.

알고리즘

시작점이나 출구가 벽이면 빈 배열을 반환합니다.
시작점을 큐에 넣습니다. 셀 (0, 0), 비트 0이 설정된 방문 집합, 이동 경로 없음으로 넣습니다.
다음 항목을 가져옵니다. 출구에 도착했다면 이동 경로를 저장하고 계속합니다.
그렇지 않으면 미로 안의 열려 있고 아직 방문하지 않은 셀로 이동하는 각 이동에 대해, 해당 셀과 그 셀의 비트를 추가한 방문 집합, 그리고 이동을 덧붙인 경로가 포함된 항목을 추가합니다.
큐가 비면 저장된 경로를 정렬하여 반환합니다.

from collections import deque


def findPaths(maze):
    n = len(maze)
    if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
        return []
    moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
    result = []
    # Each entry is a path in progress: its cell, the cells it has used
    # (bit r * n + c), and its moves so far.
    queue = deque([(0, 0, 1, "")])
    while queue:
        r, c, used, path = queue.popleft()
        if r == n - 1 and c == n - 1:
            result.append(path)
            continue
        for letter, dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
                bit = 1 << (nr * n + nc)
                if not used & bit:
                    queue.append((nr, nc, used | bit, path + letter))
    result.sort()  # shorter paths were found first, so sort by text
    return result

알파벳 순서로 백트래킹

핵심 아이디어

재귀 함수는 한 칸에 위치합니다. 출구에 도달하면 이동 경로를 저장합니다. 그렇지 않으면 경로가 되돌아오지 못하도록 해당 칸을 0으로 설정하고, 이동할 수 있는 각 칸으로 이동을 시도한 다음, 나중 경로가 그 칸을 통과할 수 있으므로 해당 칸을 다시 1로 설정합니다. 메모리에는 현재 경로가 저장되며 재귀 깊이는 최대 n²입니다.

두 경로는 처음으로 이동이 달라지는 지점까지 같은 이동을 공유하며, 그 지점에서는 검색이 알파벳 순서상 더 앞선 문자의 분기를 먼저 완료합니다. 경로는 출구에서 멈추기도 하므로 어떤 경로도 다른 경로의 시작이 되지 않습니다. 이동을 D, L, R, U 순서로 시도하므로 경로는 정렬된 순서로 저장됩니다.

알고리즘

시작점이나 출구가 벽이면 빈 배열을 반환합니다.
backtrack(r, c)를 작성합니다. (r, c)가 출구라면 현재 이동 경로를 저장하고 반환합니다.
maze[r][c]를 0으로 설정합니다.
미로 안의 열린 칸에 도달하는 D, L, R, U 순서의 각 이동에 대해 해당 문자를 추가하고, 재귀 호출한 다음 문자를 제거합니다.
maze[r][c]를 다시 1로 설정합니다. backtrack(0, 0)을 호출하고 저장된 경로를 반환합니다.

def findPaths(maze):
    n = len(maze)
    result = []
    if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
        return result
    # The moves in alphabetical order, so the paths come out sorted.
    moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
    path = []

    def backtrack(r, c):
        if r == n - 1 and c == n - 1:
            result.append("".join(path))
            return
        maze[r][c] = 0  # block the cell while this path uses it
        for letter, dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
                path.append(letter)
                backtrack(nr, nc)
                path.pop()
        maze[r][c] = 1  # open it again for the other paths

    backtrack(0, 0)
    return result

함정과 경계 사례

되돌아갈 때 칸의 표시를 지우지 않는 것. 그러면 해당 칸이 계속 막힌 상태로 남아 이후의 어떤 분기도 그 칸을 지나갈 수 없습니다. 열린 3 × 3 미로에서는 DDRR와 DDRURD를 반환하는데, 이는 12개의 경로 중 2개입니다.
시작점이나 출구가 벽일 수 있다는 점을 잊는 것. 두 번째 예시처럼 출구가 벽이면, 출구 옆에서 끝나는 경로가 아니라 빈 답을 반환해야 합니다.
아래쪽, 위쪽, 왼쪽, 오른쪽 순서로 이동을 시도하는 것. 경로 집합은 맞지만 순서는 틀립니다. 알파벳순은 D, L, R, U입니다.

자주 묻는 질문3

Rat in a Maze의 시간 복잡도는 얼마인가요?

첫 번째 이동 후에는 경로가 각 칸에서 최대 세 가지 선택지를 가지며, 최대 n²개의 칸을 방문하므로, 부분 경로는 O(3^(n²))개이고 각 경로를 기록하는 데 O(n²)의 비용이 듭니다. 벽과 이미 방문한 칸은 이 수를 크게 줄여 줍니다.

백트래킹할 때 방문 표시를 제거해야 하는 이유는 무엇인가요?

표시는 "현재 경로에 있음"을 뜻해야지, "이전에 봄"을 뜻하면 안 됩니다. 서로 다른 두 경로가 같은 칸을 지날 수 있습니다. 검색이 해당 칸에서 되돌아 나온 뒤에도 칸에 표시가 남아 있으면, 그 칸을 지나는 이후의 모든 경로를 놓치게 됩니다.

쥐가 오른쪽과 아래쪽으로만 이동할 수 있다면 어떨까요?

그러면 어떤 경로도 셀을 다시 방문할 수 없으므로 방문 표시가 필요하지 않고, 모든 경로는 정확히 2n-2번 이동합니다. 경로 수 세기는 동적 프로그래밍으로 바뀝니다. 한 셀에 도달하는 방법의 수는 그 위쪽의 열린 셀에 도달하는 방법의 수와 왼쪽의 열린 셀에 도달하는 방법의 수를 더한 것입니다.

def findPaths(maze):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

인자

maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]

예상 출력

["RDDRDR", "RDRDDR"]