[백준(BOJ)] #1194- 달이 차오른다, 가자. (파이썬, PyPy3)

문제

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

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

 

---

문제 풀이

BFS와 비트마스크 활용

 

2022.07.14 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

[파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

2022.07.15 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 비트마스크(BitMask)

[파이썬으로 배우는 알고리즘] 비트마스크(BitMask)

 

열쇠 획득

a, b, c, d, e, f 총 여섯 개의 열쇠를 비트로 나타냅니다.

열쇠	비트	십진수
a	0 0 0 0 0 1	1
b	0 0 0 0 1 0	2
c	0 0 0 1 0 0	4
d	0 0 1 0 0 0	8
e	0 1 0 0 0 0	16
f	1 0 0 0 0 0	32

 

열쇠를 아무것도 가지고 있지 않은 상태를 0(이진수 000000)으로 가정해봅시다.

현재 상태	비트	십진수
아무 열쇠도 없음	0 0 0 0 0 0	0

 

미로를 탐색하다가 b라는 열쇠를 발견합니다. 열쇠 b는 2(이진수 000010)로 원래 상태와 열쇠 b를 OR 연산을 하여 열쇠 b를 획득한 상태를 유지하게 됩니다. 000000 | 000010 = 000010(십진수 2)

현재 상태	비트	십진수
b 열쇠 소지	0 0 0 0 1 0	2

 

이어서 미로를 탐색하다가 f라는 열쇠를 발견합니다. 열쇠 f는 2(이진수 100000)로 원래 상태와 열쇠 f를 OR 연산을 하여 열쇠 f를 획득한 상태를 유지하게 됩니다. 100000 | 000010 = 100010(십진수 34)

현재 상태	비트	십진수
b, f 열쇠 소지	1 0 0 0 1 0	34

 

이렇게 획득할 수 있는 열쇠는 a, b, c, d, e, f로 표현할 수 있는 수는 최대 63(이진수 111111)입니다.

현재 상태	비트	십진수
a, b, c, d, e, f 열쇠 소지	1 1 1 1 1 1	63

 

문 열기

미로에서 특정 문에 도착했을 때는 AND 연산으로 문을 열 수 있는지 없는지 확인할 수 있습니다.

문도 열쇠와 마찬가지로 각 알파벳에 맞춰 비트로 나타냅니다.

문	비트	십진수
A	0 0 0 0 0 1	1
B	0 0 0 0 1 0	2
C	0 0 0 1 0 0	4
D	0 0 1 0 0 0	8
E	0 1 0 0 0 0	16
F	1 0 0 0 0 0	32

 

a, b, c 열쇠를 소지하고 있는 상태에서 문 B에 도착합니다.

현재 상태	비트	십진수
a, b, c 열쇠 소지	0 0 0 1 1 1	7

문 B는 000010이고 현재 상태는 000111입니다. 이제 이 둘을 AND 연산시킵니다. AND 연산하여 얻을 수 있는 값은 000010 & 000111 = 000010(십진수 2)이고 0이 아니므로 문을 열 수 있게 됩니다.

 

이번엔 a, b, c 열쇠를 소지하고 있는 상태에서 문 F에 도착합니다.

문 F는 100000이고 현재 상태는 000111입니다. 이제 이 둘을 AND 연산시킵니다. AND 연산하여 얻을 수 있는 값은 100000 & 000111 = 000000(십진수 0)이고 0이므로 문을 열 수 없습니다.

 

BFS

열쇠를 갖고 있는 상태는 0~63으로 크기가 64입니다. 이 상태를 S로 두고 N x M x S인 3차원 리스트를 사용해 미로를 탐색하며 열쇠 상태에 따른 이동 횟수를 구하면 됩니다.

 

---

구현

코드

import sys
from collections import deque
input = sys.stdin.readline

if __name__ == "__main__":
    N, M = map(int, input().split())
    board = [list(input().rstrip()) for _ in range(N)]

	# 시작 좌표구하기
    def get_start_point():
        for i in range(N):
            for j in range(M):
                if board[i][j] == '0':
                    return i, j

    def bfs(p):
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]

        visited = [[[0] * 64 for _ in range(M)] for _ in range(N)]
        dq = deque()
        total_cnt = -1
        x, y = p
        dq.append((x, y, 0))
        visited[x][y][0] = 1

        while dq:
            tx, ty, tz = dq.popleft()
            if board[tx][ty] == '1':
                total_cnt = visited[tx][ty][tz] - 1
                break
            for k in range(4):
                x = tx + dx[k]
                y = ty + dy[k]
                # 범위를 벗어났거나 방문했거나 벽일 경우
                if not (0 <= x < N and 0 <= y < M and visited[x][y][tz] == 0 and board[x][y] != '#'):
                    continue
                # 열쇠인 경우
                if board[x][y] in ['a', 'b', 'c', 'd', 'e', 'f']:
                    z = tz | (1 << (ord(board[x][y]) - ord('a')))
                    if visited[x][y][z] == 0:
                        visited[x][y][z] = visited[tx][ty][tz] + 1
                        dq.append((x, y, z))
                # 문인 경우
                elif board[x][y] in ['A', 'B', 'C', 'D', 'E', 'F']:
                    if tz & (1 << (ord(board[x][y]) - ord('A'))):
                        visited[x][y][tz] = visited[tx][ty][tz] + 1
                        dq.append((x, y, tz))
                # 길인 경우
                else:
                    visited[x][y][tz] = visited[tx][ty][tz] + 1
                    dq.append((x, y, tz))
        return total_cnt

    p = get_start_point()
    print(bfs(p))

 

결과