백준 1194 달이 차오른다, 가자.

https://www.acmicpc.net/problem/1194

문제 이해는 되게 간단하다. 0에서 1로 가는데 그사이 열쇠를 먹어서 문을 열면 된다.
문제를 보면 키1개로 1개의 문만 여는것이 아니라 해당되는 문은 다 열 수 있다.
이 점과 키가 6개밖에 없다는 점에서 아 이거 비트마스킹으로 접근하면 좋겠다고 생각했다.
왜나하면 현재 상태에서 가질 수 있는 키의 상태는 최대 2^7-1까지 이다
그렇기 때문에 bfs를 하면서 어떤 문을 만난다면 해당 문과 비트마스킹을 통해 열쇠가 있는지 확인하면 되겠다고 생각했다.

그렇다면 bfs를 어떻게 할까 생각했고 bfs를 하며 방문배열을 어떻게 할까라고 생각했다.
방문배열을 2차원으로 설정하면 만약 예제 3번에서 키 a를 획득했다면 아래로 갈수가 없었다.
그렇기 때문에 아, 해당 상태에 이러이러한 키를 획득했다고 비트로 표현해주고 상태를 한차원 더 높이면 좋겠다고 생각했다.
결국 3차원 방문배열로 0~127까지의 상태를 표현하게 해주었다.

from collections import deque
n,m = map(int,input().split())
arr = []
key = ['a','b','c','d','e','f']
doors = ['A','B','C','D','E','F']
sx = 0; sy = 0;
for i in range(n):
    x = list(input())
    for j in range(m):
        if x[j] == '0':
            sx = i; sy = j
    arr.append(x)
arr[sx][sy] = '.'
ans = -1
dx = [-1,0,1,0]
dy = [0,1,0,-1]
visited = [[[0]*128 for i in range(m)] for i in range(n)]
def bfs(x,y):
    global ans
    q = deque([])
    q.append((x,y,0))
    while q:
        x,y,now_key = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m or arr[nx][ny] == '#' or visited[nx][ny][now_key]:
                continue
            if arr[nx][ny] in key:
                idx = key.index(arr[nx][ny])
                new_key = now_key | (2<<idx)
                visited[nx][ny][new_key] = visited[x][y][now_key] + 1
                q.append((nx,ny,new_key))
            elif arr[nx][ny] in doors:
                idx = doors.index(arr[nx][ny])
                if now_key & (2<<idx):
                    visited[nx][ny][now_key] = visited[x][y][now_key] + 1
                    q.append((nx,ny,now_key))
            elif arr[nx][ny] == '1':
                ans = visited[x][y][now_key] + 1
                return
            elif arr[nx][ny] == '.':
                visited[nx][ny][now_key] = visited[x][y][now_key] + 1
                q.append((nx,ny,now_key))
bfs(sx,sy)
print(ans)
# print(visited)