이번 문제는 BFS와 비트마스킹을 통해 해결하였다. 처음 이 문제에 접근할 때, 열쇠를 주울 때마다 방문처리 리스트를 초기화하면 문제가 풀릴거라는 생각을 가지게 되었고, 큐에 방문처리 리스트를 담는 방법을 택했다. 결과는 당연히 메모리 초과가 발생하였다.

새로운 방문처리 방법에 대해 생각하던 중, 비트마스킹을 사용한 풀이를 보게 되었다. 방문처리 리스트를 3차원 리스트로 선언하는데, y, x, key의 형태로 구현되어 있었다. 이때 key는 2진수로 111111과 같이 표현할 수 있었고, 이는 64이므로 크기가 64가 되었다. 즉, 초기의 key는 000000일 것이고, 열쇠를 주우면 or연산자와 1<<ord(grid[ny][nx])-ord('a')를 사용하여 열쇠를 갱신하였다. 열쇠가 필요한 칸에 도착하면 and연산자와 1<<ord(grid[ny][nx])-ord('A')를 사용하여 열쇠의 여부를 확인하였다.

1<<ord(grid[ny][nx])-ord('a')의 결과를 정리해보면 다음과 같이 정리된다.

print(1<<ord('a')-ord('a')) # 소문자 중 0번째 문자이므로 2^0인 1(1)이 반환
print(1<<ord('b')-ord('a')) # 소문자 중 1번째인 문자이므로 2^1인 10(2)가 반환
print(1<<ord('f')-ord('a')) # 소문자 중 5번째인 문자이므로 2^5인 10000(32)가 반환

대문자의 경우 역시 마찬가지이다.

여기서 and연산자(&)와 or연산자(|)를 사용하면 다음과 같다.

print(32&2) # 0. -> 10000 & 10 = 0
print(2&2) # 2. -> 10 & 10 = 10
print(32|2) # 34. -> 10000 | 10 = 10010

이를 이용하여 방문처리를 하였고, 이를 통해 해결할 수 있었다.

Code

from collections import deque
n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
sy, sx = 0, 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == '0':
            sy, sx = i, j
            grid[i][j] = '.'
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
visited = [[[0 for _ in range(64)] for _ in range(m)] for _ in range(n)]
mapping = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5}
def bfs():
    q = deque()
    q.append((sy, sx, 0))
    visited[sy][sx][0] = 1
    while q:
        y, x, key = q.popleft()
        if grid[y][x] == '1':
            return visited[y][x][key]-1
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and grid[ny][nx] != '#' and not visited[ny][nx][key]:
                if str(grid[ny][nx]).isalpha():
                    if ord(str(grid[ny][nx])) < ord('a'):
                        if key & (1<<(ord(str(grid[ny][nx]))-ord('A'))):
                            visited[ny][nx][key] = visited[y][x][key]+1
                            q.append((ny, nx, key))
                    else:
                        new_key = key | (1<<ord(str(grid[ny][nx]))-ord('a'))
                        if not visited[ny][nx][new_key]:
                            visited[ny][nx][new_key] = visited[y][x][key]+1
                            q.append((ny, nx, new_key))
                else:
                    visited[ny][nx][key] = visited[y][x][key]+1
                    q.append((ny, nx, key))
    return -1
print(bfs())