[백준]1194 달이차오른다가자 #bfs#비트마스킹

1. 풀이

열쇠를 하나 획득하면, 이전에는 못갔던 길을 다시 가는것이 가능해질 수도 있다. 따라서 5개의 열쇠(a,b,c,d,e,f)를 갖는 경우의 수를 각각다 다르게 생각해주어야 한다.

(1) 비트마스크

이때 경우의 수를 비트마스크로 처리해준다 => (a,b,c,d,e,f) 열쇠를 각각 갖고있으면 1, 아니면 0으로 나타내 줄 수 있는 2진수를 고려해 준다.

ex)

모두 갖고있음 -> 111111

a,b,c,만 갖고있음 -> 111000

a,f만 갖고있음 -> 100001

모두 안갖고있음-> 000000

(2) bfs

열쇠를 하나 찾으면 지금까지 찾아진 열쇠에 해당하는 층으로 이동하여 (마치 벽부수고 이동하기처럼) 새로운 2차원 visited 리스트에서 탐색을 시작한다.

(새로운 열쇠를 찾으면 이전에 못갔던 곳을 다시 가는것이 가능해 질 수도 있기 때문에.)

=> 열쇠 a를 찾은경우 : 000000(0층)

=> 열쇠 a와 f를 찾은 경우 : 100001(33층)

그러면 경우의 수는 2^5=64가 나오므로 visited[N][M][64]으로 visited 리스트를 관리해주면 된다.

​

2. 소스코드

from collections import deque
dR=[0,0,-1,1]
dC=[1,-1,0,0]


#입력받기
N,M=map(int,input().split())
L=[]
for i in range(N):
    L.append(list(input()))
#시작점, 끝점찾기
srt=[0,0]
fin=[0,0]
for i in range(N):
    for j in range(M):
        if L[i][j]=="0":
            srt[0]=i
            srt[1]=j
        elif L[i][j]=="1":
            fin[0]=i
            fin[1]=j
ans=-1
#큐시작
visited=[[[-1 for key in range(64)] for j in range(M)] for i in range(N)]
visited[srt[0]][srt[1]][0]=0
q=deque([[srt[0],srt[1],0]])
while(q):
    isFind=False
    r,c,key=q.popleft()
    binKey=bin(key)[2:]
    binKey=binKey.zfill(6)
    for k in range(4):
        tempR=r+dR[k]
        tempC=c+dC[k]
        if 0<=tempR<N and 0<=tempC<M and visited[tempR][tempC][key]==-1:
            #빈곳
            if L[tempR][tempC]==".":
                visited[tempR][tempC][key]=visited[r][c][key]+1
                q.append([tempR,tempC,key])
            #벽
            elif L[tempR][tempC]=="#":
                continue
            #열쇠
            elif 97<=ord(L[tempR][tempC])<=102:
                visited[tempR][tempC][key]=visited[r][c][key]+1
                #추가되는 키의 인덱스
                addedKeyIndx=ord(L[tempR][tempC])-97
                keyL=list(binKey)
                keyL[addedKeyIndx]="1"
                temp=int("".join(keyL))
                tempKey=int("0b"+str(temp),2)
                visited[tempR][tempC][tempKey]=visited[r][c][key]+1
                q.append([tempR,tempC,tempKey])
            #문
            elif 65<=ord(L[tempR][tempC])<=70:
                doorIndx=ord(L[tempR][tempC])-65
                if int(binKey[doorIndx]):
                    visited[tempR][tempC][key] = visited[r][c][key] + 1
                    q.append([tempR,tempC,key])
            #출발지(다른열쇠획득후겠지?)
            elif L[tempR][tempC]=="0":
                visited[tempR][tempC][key] = visited[r][c][key] + 1
                q.append([tempR, tempC, key])
            #도착
            else:
                ans=visited[r][c][key]+1
                isFind=True
    if isFind:
        break
print(ans)