[백준/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
어.렵.다.
Author And Source
이 문제에 관하여([백준/python/1194]달이 차오른다,가자), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@i_am_developer/백준python1194달이-차오른다가자저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)