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

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

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

비트마스킹을 활용한 BFS입니다. 현재 가지고 있는 열쇠를 저장하고 있어야하는데 이를 비트마스킹을 활용하여 저장하고 있습니다. 예를 들어, 'a' 열쇠를 가지고 있는데 'f'열쇠가 추가된다고 하면 (1 << 'a' - 'a') | (1 << 'f' - 'a')를 하여 1000001을 저장하고 있으면 되고 열쇠가 있는지 체크할 때에도 마찬가지 원리를 활용하면 됩니다. visited배열도 현재 열쇠 조합을 가지고 (i, j)를 방문했는지 여부를 체크해야하기 때문에 3차원으로 관리되어야만 합니다.

 

import sys
from collections import deque
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

board = [
    list(input().rstrip())
    for _ in range(n)
]

start = (-1, -1)

for i in range(n):
    for j in range(m):
        if board[i][j] == '0':
            start = (i, j)
            board[i][j] = '.'

# visited[k][i][j]: k열쇠를 가지고 (i, j)를 방문한 경우
visited = [
    [[False] * m
    for _ in range(n)]
    for __ in range(1 << 6)
]

q = deque([(start[0], start[1], 0, 0)])

dys= [0, 1, 0, -1]
dxs = [1, 0, -1, 0]

visited[0][start[0]][start[1]] = True

def inRange(y, x):
    return 0 <= y < n and 0 <= x < m

while q:
    y, x, d, key = q.popleft()

    if board[y][x] == '1':
        print(d)
        sys.exit(0)

    for dy, dx, in zip(dys, dxs):
        ny = y + dy
        nx = x + dx

        if inRange(ny, nx) and board[ny][nx] != '#':
            # 다음이 열쇠인 경우
            if 'a' <= board[ny][nx] <= 'f':
                diff = ord(board[ny][nx]) - ord('a')
                nextKey = key | (1 << diff)
                #다음 열쇠로 다음을 방문하지 않은 경우에만 방문
                if not visited[nextKey][ny][nx]:
                    visited[nextKey][ny][nx] = True
                    q.append((ny, nx, d + 1, nextKey))
            # 다음이 문인 경우
            elif 'A' <= board[ny][nx] <= 'F':
                diff = ord(board[ny][nx]) - ord('A')
                if ((1 << diff) & key) == (1 << diff) and not visited[key][ny][nx]:
                    visited[key][ny][nx] = True
                    q.append((ny, nx, d + 1, key))
            # 빈칸, 출구인 경우
            else:
                if not visited[key][ny][nx]:
                    visited[key][ny][nx] = True
                    q.append((ny, nx, d + 1, key))


print(-1)