[BOJ 1194] 달이 차오른다, 가자(Python)

문제

달이 차오른다, 가자

---

문제 해설

bfs와 비트마스크를 활용하여 푸는 문제입니다. 키를 가지고 이동하는 문제이기 때문에 방문 체크 리스트를 3차원으로 확장하여 풀어야 합니다. 방문 체크 리스트는 boolean, int 둘 중 선택하여 풀 수 있습니다.

4방 탐색을 이용하여 움직이는데 조건이 있습니다.
1. 범위 안이어야 한다.
2. 벽이 아니어야 한다.
3. 동일한 키를 가지고 그곳에 방문한 적이 없어야 한다.

그렇다면 동일한 키를 가지고 있는지에 대한 판단을 어떻게 해야 할까요?
[x][y][key]와 같이 x,y좌표와 그곳에 대한 key값에 대한 리스트에 접근하여 그곳이 0인지 판단하면 됩니다(boolean인 경우 False).

key는 주어진 키가 a~f까지기 때문에 000000 ~ 111111의 비트를 사용합니다. 그렇기때문에 key의 범위는 0~63까지 입니다.

문을 만난다면 열쇠를 확인하는데, 현재 가지고 있는 열쇠와 문을 &연산을 통해 확인합니다. 현재 a,d를 가지고 있다면 1001, D문을 만나면 1000, 이 두 값을 and 연산을 통해 판단할 수 있습니다.

열쇠를 만난다면 현재의 키값에 획득할 키와 |연산을 진행하면 됩니다. 현재 a,d를 가지고 있고 c키를 만난다면 1001 | 100 -> 1101이 됩니다.

---

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(str, input().rstrip())) for _ in range(n)]
visited = [[[0] * 64 for _ in range(m)] for _ in range(n)]
dx = -1, 0, 1, 0
dy = 0, 1, 0, -1
q = deque()

for i in range(n):
    for j in range(m):
        if graph[i][j] == "0":
            graph[i][j] = "."
            q.append((i, j, 0))
            break

while q:
    x, y, key = q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        nkey = key
        # 범위 안 이면서 벽도 아니고 동일한 키를 가지고 그곳에 방문한 적이 없어야 한다.
        if (
            0 <= nx < n
            and 0 <= ny < m
            and graph[nx][ny] != "#"
            and visited[nx][ny][key] == 0
        ):
            # 문인 경우
            # 열쇠가 없으면 continue
            # & 연산으로 1 혹은 0이 나오게 된다.
            if graph[nx][ny].isupper():
                if not (key & 1 << (ord(graph[nx][ny]) - ord("A"))):
                    continue
            # 열쇠인 경우
            # or 연산을 통해 key를 교체
            # a키만 가지고 c키를 먹는다면
            # 1 -> 101이 된다.
            elif graph[nx][ny].islower():
                nkey |= 1 << ord(graph[nx][ny]) - ord("a")
            elif graph[nx][ny] == "1":
                print(visited[x][y][key] + 1)
                exit()
            q.append((nx, ny, nkey))
            visited[nx][ny][nkey] = visited[x][y][key] + 1
print(-1)

---