[리트코드] 864 - Shortest Path to Get All Keys

864. Shortest Path to Get All Keys

Hard

---

You are given an m x n grid grid where:

• '.' is an empty cell.
• '#' is a wall.
• '@' is the starting point.
• Lowercase letters represent keys.
• Uppercase letters represent locks.

You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.

If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.

For some 1 <= k <= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it is impossible, return -1.

 

Example 1:

Input: grid = ["@.a..","###.#","b.A.B"]
Output: 8
Explanation: Note that the goal is to obtain all the keys not to open all the locks.

Example 2:

Input: grid = ["@..aA","..B#.","....b"]
Output: 6

Example 3:

Input: grid = ["@Aa"]
Output: -1

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 30
• grid[i][j] is either an English letter, '.', '#', or '@'. 
• There is exactly one '@' in the grid.
• The number of keys in the grid is in the range [1, 6].
• Each key in the grid is unique.
• Each key in the grid has a matching lock.

분류

배열, 비트 조작, 너비 우선 탐색, 행렬

---

문제 풀이

문제 분석

이 문제는 m x n 크기의 격자(grid)에서 시작점(@)부터 출발하여 모든 열쇠를 수집하는 데 필요한 최소 이동 횟수를 찾는 문제입니다. 격자는 빈 칸(.), 벽(#), 시작점(@), 소문자 열쇠, 대문자 잠금장치로 구성됩니다. 한 번의 이동으로 상하좌우 네 방향 중 한 칸을 움직일 수 있으며, 격자 밖으로 나가거나 벽으로는 이동할 수 없습니다.

열쇠를 획득하면 해당 열쇠에 대응하는 잠금장치를 통과할 수 있습니다. 예를 들어, 'a' 열쇠를 가지고 있으면 'A' 잠금장치를 통과할 수 있습니다. 각 열쇠에는 정확히 하나의 대응하는 잠금장치가 있으며, 격자 내 열쇠의 개수 k는 1에서 6 사이입니다. 즉, 열쇠는 최대 6개입니다. 목표는 모든 열쇠를 수집하는 것이며, 모든 잠금장치를 여는 것이 아닙니다. 모든 열쇠를 수집할 수 없다면 -1을 반환합니다.

접근 방법

이 문제는 최단 경로를 찾는 문제이므로 **너비 우선 탐색(BFS)**을 사용하는 것이 적합합니다. 하지만 단순히 (행, 열) 위치만으로는 현재 상태를 완전히 정의할 수 없습니다. 왜냐하면 어떤 열쇠를 가지고 있는지에 따라 갈 수 있는 경로가 달라지기 때문입니다. 따라서 BFS의 각 상태는 현재 위치 (행, 열)뿐만 아니라 현재까지 획득한 열쇠 정보를 함께 포함해야 합니다.

획득한 열쇠 정보는 최대 6개의 열쇠가 존재하므로, 비트마스크(bitmask)를 사용하여 효율적으로 표현할 수 있습니다. 예를 들어, 첫 번째 열쇠('a')는 0번 비트, 두 번째 열쇠('b')는 1번 비트 등으로 매핑하여, 특정 비트가 1이면 해당 열쇠를 가지고 있음을 나타냅니다.

따라서 BFS의 각 상태는 (현재 행, 현재 열, 이동 횟수, 획득한 열쇠 비트마스크)가 됩니다. 방문 여부를 추적하는 visited 배열도 visited[행][열][획득한 열쇠 비트마스크] 형태의 3차원 배열로 정의하여, 특정 위치에 특정 열쇠 세트를 가지고 도달한 적이 있는지 여부를 기록합니다.

구현 설명

1단계: 초기화 및 전처리

• 격자 변환 및 시작점 찾기: 입력 grid를 문자 리스트의 리스트(g)로 변환하여 접근을 용이하게 합니다. 시작점(@)을 찾아 start 변수에 저장하고, 해당 위치는 빈 칸(.)으로 변경합니다.
• 열쇠 인덱싱: 격자를 순회하면서 모든 소문자 열쇠를 찾고, keys_idx 딕셔너리에 각 열쇠 문자를 0부터 keys_cnt-1까지의 고유한 정수 인덱스에 매핑합니다. keys_cnt는 전체 열쇠의 개수를 나타냅니다. 이 인덱스는 비트마스크에서 해당 열쇠의 비트 위치를 결정하는 데 사용됩니다.
• 목표 비트마스크 설정: 모든 열쇠를 획득했을 때의 비트마스크 target을 (1 << keys_cnt) - 1로 계산합니다. 예를 들어, 열쇠가 3개라면 111 (이진수)이 됩니다.
• BFS 초기화: visited 3차원 배열을 False로 초기화합니다. 크기는 n x m x (1 << keys_cnt)입니다. deque를 BFS 큐로 사용하며, 시작 상태 (start_x, start_y, 0, 0) (시작 위치, 0 이동, 0 열쇠)를 큐에 추가하고 해당 상태를 visited에 True로 표시합니다. directions는 상하좌우 이동을 위한 튜플 리스트입니다.

2단계: BFS 탐색

• 큐가 비어있지 않은 동안 반복합니다.
• 큐에서 가장 오래된 상태 (x, y, cnt, key_mask)를 꺼냅니다. (x, y)는 현재 위치, cnt는 현재까지의 이동 횟수, key_mask는 현재 가지고 있는 열쇠들의 비트마스크입니다.
• 네 가지 방향(상하좌우)으로 이동을 시도합니다. 다음 위치 (sx, sy)를 계산합니다.
• 유효성 검사: (sx, sy)가 격자 범위 내에 있는지 확인합니다.

3단계: 다음 상태 처리

• 벽인 경우: g[sx][sy]가 벽('#')이면 이동할 수 없으므로 다음 방향으로 넘어갑니다.
• 빈 칸인 경우: g[sx][sy]가 빈 칸('.')인 경우:
  • 만약 (sx, sy) 위치에 현재 key_mask 상태로 방문한 적이 없다면:
    • queue.append((sx, sy, cnt + 1, key_mask))를 통해 큐에 추가하고, visited[sx][sy][key_mask]를 True로 설정합니다. 이동 횟수는 cnt + 1이 됩니다.
• 열쇠인 경우: g[sx][sy]가 소문자(열쇠)인 경우:
  • 현재 가지고 있는 열쇠 key_mask에 새로 얻은 열쇠를 추가하여 next_key_mask를 만듭니다: key_mask | (1 << keys_idx[g[sx][sy]]).
  • next_key_mask가 target과 같다면, 모든 열쇠를 수집한 것이므로 cnt + 1을 반환합니다. 이것이 최단 경로입니다.
  • 만약 (sx, sy) 위치에 next_key_mask 상태로 방문한 적이 없다면:
    • queue.append((sx, sy, cnt + 1, next_key_mask))를 통해 큐에 추가하고, visited[sx][sy][next_key_mask]를 True로 설정합니다.
• 잠금장치인 경우: g[sx][sy]가 대문자(잠금장치)인 경우:
  • 해당 잠금장치에 필요한 열쇠의 인덱스 door_idx를 찾습니다: keys_idx[g[sx][sy].lower()].
  • 현재 key_mask에 door_idx에 해당하는 열쇠가 있는지 확인합니다: key_mask & (1 << door_idx).
  • 만약 열쇠를 가지고 있고, (sx, sy) 위치에 현재 key_mask 상태로 방문한 적이 없다면:
    • queue.append((sx, sy, cnt + 1, key_mask))를 통해 큐에 추가하고, visited[sx][sy][key_mask]를 True로 설정합니다. (열쇠는 변하지 않음)

4단계: 결과 반환

• 큐가 비어질 때까지 모든 경로를 탐색했음에도 target에 도달하지 못했다면, 모든 열쇠를 수집하는 것이 불가능하다는 의미이므로 -1을 반환합니다.

⏱복잡도 분석

• 시간 복잡도: O(N * M * 2^K)

  • N은 격자의 행 수 (n), M은 격자의 열 수 (m)입니다.
  • K는 격자 내 열쇠의 총 개수 (keys_cnt)입니다. 문제 조건에 따라 K <= 6입니다.
  • BFS의 각 상태는 (행, 열, 열쇠 비트마스크)로 구성됩니다. 가능한 행의 수는 n, 열의 수는 m, 열쇠 비트마스크의 수는 2^K개입니다.
  • 따라서 방문할 수 있는 총 상태의 수는 n * m * 2^K개입니다.
  • 각 상태는 큐에 한 번 추가되고 한 번 제거됩니다. 각 상태에서 최대 4방향을 탐색하는 데 상수 시간이 걸립니다.
  • 최악의 경우, 모든 상태를 방문해야 할 수 있으므로 시간 복잡도는 O(n * m * 2^K)가 됩니다. 30 * 30 * 2^6 = 900 * 64 = 57600으로, 충분히 빠른 시간 내에 해결 가능합니다.

• 공간 복잡도: O(N * M * 2^K)

  • visited 배열은 n * m * 2^K 크기의 부울 값을 저장합니다.
  • queue는 최악의 경우, 모든 상태를 저장할 수 있으므로 n * m * 2^K 크기가 될 수 있습니다.
  • 따라서 공간 복잡도는 O(n * m * 2^K)가 됩니다.

핵심 포인트

1. BFS (너비 우선 탐색) 사용: 최단 경로를 찾아야 하므로 BFS가 가장 적합한 알고리즘입니다. 각 단계에서 현재 위치와 획득한 열쇠 상태를 바탕으로 다음 단계로 나아가면서, 가장 먼저 목표(모든 열쇠 획득)에 도달하는 경로가 최단 경로가 됩니다.
2. 비트마스크를 이용한 열쇠 상태 관리: 열쇠의 개수가 최대 6개로 적기 때문에, 비트마스크를 사용하여 현재 획득한 열쇠의 조합을 효율적으로 표현할 수 있습니다. 각 열쇠에 고유한 비트를 할당하고, 열쇠를 획득할 때마다 해당 비트를 1로 설정하여 상태를 갱신합니다. 이 비트마스크는 BFS의 핵심 상태 정보 중 하나입니다.
3. visited 배열의 3차원 확장: 단순히 visited[행][열]만으로는 부족하며, visited[행][열][획득한 열쇠 비트마스크] 형태로 visited 배열을 확장해야 합니다. 이는 동일한 (행, 열) 위치에 도달했더라도 획득한 열쇠 조합이 다르면 다른 상태로 간주되어야 하기 때문입니다. 이 3차원 visited 배열을 통해 중복 계산을 방지하고 무한 루프에 빠지는 것을 막을 수 있습니다.

풀이 코드

from collections import deque

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        g = []
        for x in grid:
            g.append(list(x))

        n = len(g)
        m = len(g[0])
        keys_cnt = 0
        keys_idx = {}
        for i in range(n):
            for j in range(m):
                if g[i][j] == "@":
                    start = [i,j]
                    g[i][j] = "."
                elif g[i][j].islower():
                    keys_idx[g[i][j]] = keys_cnt
                    keys_cnt += 1

        visited = [[[False] * (1 << keys_cnt) for _ in range(m)] for _ in range(n)]
        
        queue = deque([(start[0],start[1],0,0)])
        visited[start[0]][start[1]][0] = True
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        target = (1 << keys_cnt) - 1
        while queue:
            x,y,cnt,key = queue.popleft()
            for dx,dy in directions:
                sx,sy = x+dx,y+dy
                if 0<=sx<n and 0<=sy<m:
                    if  g[sx][sy] == "." and not visited[sx][sy][key]:
                        queue.append((sx,sy,cnt+1,key))
                        visited[sx][sy][key] = True
                    elif g[sx][sy].islower():
                        next_key = key | (1 << keys_idx[g[sx][sy]])
                        if next_key == target:
                            return cnt + 1
                        if not visited[sx][sy][next_key]:
                            queue.append((sx,sy,cnt+1,next_key))
                            visited[sx][sy][next_key] = True
                    elif g[sx][sy].isupper() and not visited[sx][sy][key]:
                        door_idx = keys_idx[g[sx][sy].lower()]
                        if key & (1 << door_idx):
                            queue.append((sx,sy,cnt+1,key))
                            visited[sx][sy][key] = True
        return -1