백준 1194 달이 차오른다, 가자. (파이썬)

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

1194번: 달이 차오른다, 가자.

bfs로 이동한 것을 표시할 배열을 [x][y][key] 3차원으로 해서 열쇠를 2진법으로 연산하여 조건에 맞게 이동

 

1. 열쇠가 6개므로 2진법으로 (0~111111)까지 표현가능하므로 열쇠에 해당하는 차수를 64로 설정

2. 이동 중에 소문자를 만나면 or 연산으로 열쇠 보유를 갱신하여 큐에 입력

3. 대문자를 만나면 and 연산으로 알맞은 열쇠를 보유했는지 체크 후 이동

4. 1을 만나면 이동 경로를  출력

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    q.append([x, y, 0])
    c[x][y][0] = 1
    while q:
        x, y, z = q.popleft()
        if a[x][y] == '1':
            print(c[x][y][z] - 1)
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if a[nx][ny] != '#' and c[nx][ny][z] == 0:
                    if a[nx][ny].islower():
                        nz = z | (1 << (ord(a[nx][ny]) - ord('a')))
                        if c[nx][ny][nz] == 0:
                            c[nx][ny][nz] = c[x][y][z] + 1
                            q.append([nx, ny, nz])
                    elif a[nx][ny].isupper():
                        if z & (1 << (ord(a[nx][ny]) - ord('A'))):
                            c[nx][ny][z] = c[x][y][z] + 1
                            q.append([nx, ny, z])
                    else:
                        c[nx][ny][z] = c[x][y][z] + 1
                        q.append([nx, ny, z])
    print(-1)

n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
c = [[[0]*64 for _ in range(m)] for _ in range(n)]
q = deque()

for i in range(n):
    for j in range(m):
        if a[i][j] == '0':
            bfs(i, j)