[🥇1 / 백준 1194 / 파이썬] 달이 차오른다, 가자.

 

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

 

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 칸: 언제나 이동할 수 있다. ('.')
• 벽: 절대 이동할 수 없다. ('#')
• 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
• 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
• 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
• 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

 

 

예제 텍스트 복사는 위 링크를 참조해주시길 바랍니다.

예제 입력 1	예제 출력 1 7
예제 입력 2	예제 출력 2 -1
예제 입력 3	예제 출력 3  55
예제 입력 4	예제 출력 4  3
예제 입력 5	예제 출력 5  6
예제 입력 6	예제 출력 6  19
예제 입력 7	예제 출력 7  12
예제 입력 8	예제 출력 8  -1

 

풀이

 

비트 마스킹을 통해 얻은 열쇠 목록을 갱신해나가며 BFS를 진행하는 문제이다.

 

비트 마스킹을 하는 이유는 효율적인 조건 분기 갱신과 참조가 빠르고 메모리를 절약할 수 있기 때문이다.

필자는 키와 문의 코드를 a부터 f까지 각각 1, 2, …, 32로 배정했다.

이를 2진법으로 계산하여 비트 마스킹을 한다.

 

만약 a와 d를 얻었다면 각각 2진법으로 1, 1000 이 되는데 이를 a | b 한다면 1001이 되므로 쉽게 어느 열쇠를 얻었는 지 판단할 수 있고 갱신도 가능하다.

 

필요한 열쇠가 흩어져 있을 수 있기  때문에, 방문했던 정점을 다시 방문할 수 있어야 한다.

하지만 무조건 방문을 허용해야 하는 것은 아니다. (시간초과가 걸릴 것이다.)

현재 가지고 있는 열쇠 목록이 방문했던 정점에 기록된 열쇠 목록과 달라야만 방문을 허용할 것이다.

 

이를 염두하여 코드를 작성하자.

 

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

def solve():
    n,m = map(int,input().split())
    board = [list(input().rstrip()) for _ in range(n)]
    visit = [[-1]*m for _ in range(n)]
    key = {'a':1,'b':2,'c':4,'d':8,'e':16,'f':32}
    door = {'A':1,'B':2,'C':4,'D':8,'E':16,'F':32}
    move = [(0,1),(1,0),(0,-1),(-1,0)]

    # 시작점 찾기
    q = deque()
    for i in range(n):
        for j in range(m):
            if board[i][j] == '0':
                q.append((i,j,0,0)) # x,y,cnt,bit masking
                visit[i][j] = 0
                board[i][j] = '.'
                break
        else:
            continue
        break

    while q:
        x,y,cnt,bit = q.popleft()
        for a,b in move:
            dx=x+a; dy=y+b
            if dx>=n or 0>dx or dy>=m or 0>dy or board[dx][dy] == "#":
                continue

            # 이미 왔던 곳인데 열쇠를 더 획득하지 못한 상태
            if not visit[dx][dy] == -1 and visit[dx][dy] | bit == visit[dx][dy]:
                continue
            visit[dx][dy] = bit 

            # 처음 방문
            if visit[dx][dy] == -1:
                visit[dx][dy] = 0

            if board[dx][dy] == '.':
                q.append((dx,dy,cnt+1,bit))
                continue

            if board[dx][dy] == '1':
                print(cnt+1)
                sys.exit()

            k = key.get(board[dx][dy])
            if k != None:
                # 얻은 열쇠 목록을 비트마스킹으로 갱신
                q.append((dx,dy,cnt+1,bit|k))
                continue

            # 열쇠가 있어 문을 열 수 있는 경우 큐에 담음
            d = door.get(board[dx][dy])
            if d | bit == bit:
                q.append((dx,dy,cnt+1,bit))
    print(-1)
solve()