[백준/python/1194]달이 차오른다,가자

문제 링크 : 달이 차오른다,가자

문제의 스토리가 장황에서 처음 읽을 때는 이해되지 않았다. 자세히 읽어보니 미로문제였다. 다른 문제와 다른 점을 알파벳 키를 가질 수 있다는 것이다.

import sys
from collections import deque

input=sys.stdin.readline
n,m=map(int, input().split())
dx=[0,0,-1,1]
dy=[1,-1,0,0]

def bfs():
    while q:
        x,y,c,cnt=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m and miro[nx][ny]!="#" and visit[nx][ny][c]==0:
                if miro[nx][ny]==".":
                    visit[nx][ny][c]=1
                    q.append([nx,ny,c,cnt+1])
                elif miro[nx][ny]=="1":
                    return cnt+1
                else:
                    if miro[nx][ny].isupper():
                        if c&1<<(ord(miro[nx][ny])-65):
                            visit[nx][ny][c]=1
                            q.append([nx,ny,c,cnt+1])
                    elif miro[nx][ny].islower():
                        nc=c|(1<<ord(miro[nx][ny])-97)
                        if visit[nx][ny][nc]==0:
                            visit[nx][ny][nc]=1
                            q.append([nx,ny,nc,cnt+1])
    return -1
q=deque()
miro = []
visit=[[[0]*64 for i in range(m)]for i in range(n)]
for i in range(n):
    a=list(input().strip())
    miro.append(a)
    for j in range(m):
        if a[j]=="0":
            q.append([i,j,0,0])
            miro[i][j]="."
            visit[i][j][0]=1
print(bfs())

키를 판별해주는 과정이 너무 어려웠다. 그래서 다른 분의 블로그를 참고했다.

이 분은 이진법으로 표현했다.
1<<(ord("A")-65) 일 경우 1->1
1<<(ord("B")-65) 일 경우 2->10
1<<(ord("C")-65) 일 경우 4->100
이런식이다. 소문자도 동일하다.

&는 이진수들을 and연산하기 때문에 여러 열쇠를 주울 경우 합쳐진다.
A와 B와 D열쇠를 가진 경우->1011

|는 이진수들을 or 연산하기 때문에 열쇠를 사용한다.
1011에서 b를 만나 사용할 경우->1001

어.렵.다.