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

from collections import deque
N, M = map(int,input().split())



lower_dict = {}
upper_dict = {}

for i in range(6):
    lower_dict[chr(ord('a')+i)] = i
    upper_dict[chr(ord('A')+i)] = i

start = []
arr = []
for x in range(N):
    input_list = list(input())
    for y in range(M):
        if input_list[y] == '0':
            start = (x,y)
    arr.append(input_list)


stack = deque()
stack.append((0,start,0))
flag = True
result = []
INF = float('inf')
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited = [[[INF for _ in range(M)] for _ in range(N)] for _ in range(64)]
visited[0][start[0]][start[1]] = 0
while stack:
    time,cur_node,state = stack.popleft()
    x,y = cur_node
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] != '#' and visited[state][nx][ny] == INF:
                if arr[nx][ny] in upper_dict.keys():
                    if state & 1<<upper_dict[arr[nx][ny]]:
                        visited[state][nx][ny] = time + 1
                        stack.append((time+1,(nx,ny),state))
                elif arr[nx][ny] in lower_dict.keys():
                    visited[state][nx][ny] = time + 1
                    new_state = state | 1<< lower_dict[arr[nx][ny]]
                    visited[new_state][nx][ny] = time + 1
                    stack.append((time+1,(nx,ny),new_state))
                else:
                    if arr[nx][ny] == '1':
                        flag = False
                        result.append(time+1)
                        break
                    visited[state][nx][ny] = time + 1
                    stack.append((time+1,(nx,ny),state))
    if not flag:
        break

if flag:
    print(-1)
else:
    print(min(result))

 

 

그래프를 활용한 문제이다. 여기서 주의해야 할 점은 열쇠와 문을 열수 있는 상태를 구분하는것이다.

 

이 상태를 구분하기 위해 비트마스킹을 이용했다.

 

현재 상태에서 키가 있는 위치에 도착을 하면 OR 연산을 해서 key를 업데이트 해주고,

 

그리고 문에 도착을 하면 현재상태와 AND 연산을 해서 True가 되면, 현재 문에 대응하는 열쇠를 소유하는 것으로 판별을 해서 지나갈수 있도록 만들어 주었다.

 

 

문제에서 문과 열쇠는 A~F,a~f 밖에 없으므로,

 

2**0 ~ 2**5 까지로 각각 a~f,A~F를 매핑시켜주면 된다.

 

그리고 이 전체 state의 크기는 64개이므로, visited 배열을 64*(N*M)의 크기로 미리 만들어둔다.

 

그리고 그 외에는 일반적인 BFS와 동일하게 해주면 된다.

 

 

이 문제는 비트 마스킹을 통해 현재 가지고 있는 키의 상태를 업데이트 해주고, 문에 도착했을때, 이 문에 대응하는 키를 소유하고 있는지를 구분해주면 되는 문제였다.