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

풀이 시간

• 1h 10m

구현 방식

• 이 문제는 "9328: 열쇠" 문제와 유사하나, 차이점은 이동 횟수의 최솟값을 구하는 문제라는 점이다
  -> 또한 이 문제에선 열쇠 문제와 다르게 keys set을 이용하지 않고 비트마스킹을 이용했다

• visit 리스트를 3차원으로 선언하여 중복 방문 제거 및 door에 해당하는 key를 가지고 있는 지를 판별해주었다
  -> key가 6개이기 때문에 2**6(1 << 6)개의 bit수가 필요하다

• 1) 열쇠를 가지고 있는 지 판별
  -> 여기서 result가 True이면 해당 door의 key를 가지고 있는 경우이다

result = key & (1 << (ord(door) - ord('A')))

• 2) 열쇠 추가 연산

nkey = key | (1 << (ord(board[nx][ny]) - ord('a')))

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def haveKey(key, door):
    result = key & (1 << (ord(door) - ord('A')))
    if result: return True
    else: return False

def bfs(x, y):
    global min_cnt

    queue = deque([]); queue.append((x, y, 0, 0))
    visit = [[[False] * (1 << 6) for m in range(M)] for n in range(N)]; visit[x][y][0] = True #6개의 key -> 2**6개의 bits
    board[x][y] = '.'

    while queue:
        x, y, cnt, key = queue.popleft()
        if board[x][y] == '1':
            min_cnt = min(min_cnt, cnt); return
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if not visit[nx][ny][key]:
                    if board[nx][ny] == '.' or board[nx][ny] == '1': #빈 공간 또는 출구
                        visit[nx][ny][key] = True
                        queue.append((nx, ny, cnt+1, key))

                    elif 97 <= ord(board[nx][ny]) <= 122: #열쇠
                        nkey = key | (1 << (ord(board[nx][ny]) - ord('a')))
                        visit[nx][ny][nkey] = True
                        queue.append((nx, ny, cnt+1, nkey))

                    elif 65 <= ord(board[nx][ny]) <= 90: #문
                        if haveKey(key, board[nx][ny]):
                            visit[nx][ny][key] = True
                            queue.append((nx, ny, cnt+1, key))
    return


N, M = map(int, sys.stdin.readline()[:-1].split())

board = deque([]); start_x = -1; start_y = -1
for n in range(N):
    tmp = list(sys.stdin.readline()[:-1])
    for m in range(M):
        if tmp[m] == '0': start_x = n; start_y = m
    board.append(tmp)

min_cnt = int(10e9)
bfs(start_x, start_y)
if min_cnt == int(10e9): print(-1)
else: print(min_cnt)

결과