[백준] 1194번 : 달이 차오른다, 가자.

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

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

해당 문제는 비트마스킹 및 너비우선 탐색으로 문제를 해결 하였습니다. 깊이, 너비중 너비를 고른 이유는 최소거리를 구해야 하는 문제는 너비우선 탐색이 더 편하기 때문입니다. 키를 얻을때마다 새로운 탐색범위가 생기고 문을 다 열어보면서 1을 찾아가는 식으로 문제를 해결 하였습니다. OR 연산과 AND 연산을 통하여 Key를 등록하는 로직과 해당 Door를 방문하였을때 Key를 가지고있는 로직을 판단합니다.

visited는 3차원 키를 얻을때마다 새로운 탐색범위가 생기기때문에 key를 가질수 있는 경우의 수를 비트마스킹하여 5개의 키가 있다면 64개의 탐색범위가 생길 수 있습니다.

 

from collections import deque
N, M = map(int, input().split()) # 세로, 가로
move = [(0,1), (0,-1), (1,0), (-1,0)]
keys = ('a', 'b', 'c', 'd', 'e', 'f')
doors =  ('A', 'B', 'C', 'D', 'E', 'F')
start = []
graph = []
for i in range(N):
    char = input()
    for j in range(M):
        if char[j] == '0':
            start.append(i)
            start.append(j)
    graph.append(list(map(str, char)))


def bfs():
    visited = [ [[0 for _ in range( (1<<6))] for _ in range(M)] for _ in range(N)]
    queue = deque()
    queue.append([start[0], start[1], 0])
    graph[start[0]][start[1]] = '.'
    visited[start[0]][start[1]][0] = 0
    while queue:
        i , j, key = queue.popleft()
        for dy, dx in move:
            ny, nx = i + dy, j + dx
            newkey = key
            if N > ny >= 0 and M > nx >= 0 and not visited[ny][nx][key] and graph[ny][nx] != '#':
                if graph[ny][nx] in keys: # 키라면
                    newkey |= 1 << keys.index(graph[ny][nx])
                        
                elif graph[ny][nx] in doors: # 문이라면
                    if not (key & 1 << doors.index(graph[ny][nx])): # 키가 없다면
                       continue
                       
                elif graph[ny][nx] == '1' : # 1이라면
                    return visited[i][j][key] + 1
                
                visited[ny][nx][newkey] = visited[i][j][key] + 1
                queue.append([ny, nx, newkey])
                            
    return None
                
result = bfs()
if result == None:
    print(-1)
else:
    print(result)