백준 1194: 달이 차오른다, 가자. - 비트 마스킹, BFS (파이썬)

달이 차오른다, 가자. 성공

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을 출력한다.

 

 

 

내 코드

import sys
from collections import deque

def bfs(x,y):
    que=deque()
    que.append([x,y,0,0]) # (x,y,이동 횟수, 키 상태) 꼴로 들어간다
    visited[0][x][y]=True # 아무 키도 없는 상태이고, (x,y)에 있다는 뜻!

    while que:
        x,y,cnt,keys=que.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            if nx<0 or nx>=n or ny<0 or ny>=m: # 범위 체크
                continue

            if not visited[keys][nx][ny]: # 같은 상태, 같은 좌표로 방문하지 않았을 때만 시도한다

                # Case 1: 도착지를 만났을 때
                if arr[nx][ny]=='1':
                    print(cnt+1)
                    exit(0)

                # Case 2: 그냥 갈 수 있는 곳을 만났을 때
                elif arr[nx][ny]=='.':
                    visited[keys][nx][ny]=True
                    que.append([nx,ny,cnt+1,keys])

                # Case 3: key를 만났을 때
                elif 'a'<=arr[nx][ny]<='f':
                    updateKeys=keys | (1<<(ord(arr[nx][ny])-ord('a'))) # 해당 키를 가진 상태!
                    visited[updateKeys][nx][ny]=True # 방문 처리
                    que.append([nx,ny,cnt+1,updateKeys]) # 업데이트한 키 상태를 넘겨준다

                # Case 4: 문을 만났을 때
                elif 'A'<=arr[nx][ny]<='F':
                    if keys & (1<<ord(arr[nx][ny])-ord('A')): # 이 문에 해당하는 key를 가지고 있다면,
                        visited[keys][nx][ny]=True # 방문 가능 하다
                        que.append((nx,ny,cnt+1,keys)) # 큐에 넘겨준다

    print(-1)



# Main Code
dx=[-1,0,1,0]
dy=[0,1,0,-1]

n,m=map(int,sys.stdin.readline().split())

arr=[]
start_x,start_y=0,0
for i in range(n):
    arr.append(list(sys.stdin.readline().rstrip()))
    for j in range(m):
        if arr[i][j]=='0':
            start_x,start_y=i,j
            arr[i][j]='.' # 출발점도 그냥 갈 수 있는 칸으로 처리


# 키의 보유 현황 별로 좌표의 방문여부를 저장한다!
# ex. a,b 키를 갖고 (1,3)에 있는거랑, a,b,c,d 키를 갖고 (1,3)에 있는 것은 다른 상태이다!!
visited=[[[False]*m for _ in range(n)] for _ in range(1<<6)]

bfs(start_x,start_y)

 

풀이 및 접근)

- 해당 문제는 기본적으로 그래프 탐색, BFS 문제이다. 최단경로를 구하는 것이기 때문에 DFS가 아니라 BFS를 통해 접근한다. 하지만 방문처리를 하는 과정이 복잡했다.

 

- 필자는 처음에 keys=[False, False, False, False, False, False] 를 통해서 키 상태를 관리했다. 하지만 이를 전역으로 공통되게 사용하게 되면, 모든 상황을 커버할 수 없다. 특정 좌표에서 가질 수 있는 키의 상태는 2^6 가지 인데 말이다.

 

- 하지만 visited[2^6][x][y] 식으로 방문 처리를 관리하는 것은 매우 큰 메모리 낭비를 발생시킨다. 이것을 방지하기 위해 비트마스킹을 통해 키의 상태를 관리할 수 있다.

 

- 키가 6개 있으므로 6자리 이진수를 생각해보자.

    f e d c b a 순서대로 키가 있을 때, 키를 가지고 있으면 1, 키를 가지고 있지 않으면 0으로 세팅하여 이를 관리한다.

    예를 들어, 100110 의 상태는, f, c, b 키를 가지고 있는 상태라고 받아들일 수 있다.

 

- 이를 통해 방문처리를 visited[keys][x][y] 로 표시할 수 있다. 해당 코드의 뜻은, "keys의 키 상태로 (x,y)에 방문하였음" 이다. 특정 좌표에 방문하는 경우는, 현태 키의 상태에 따라 다른 상태로 인식되어야 하기 때문에 이런 식으로 방문배열을 처리하는 것이다.

 

- 위에서 쓰인 간단한 비트 마스킹 연산을 알아보자.

1. 비트 SET

 

    updateKeys=keys | (1<<(ord(arr[nx][ny])-ord('a')))

 

현재 키 상태에서, 내가 원하는 키 위치의 값을 1로 바꿔주는 코드이다.

 

2. 비트 조회 (Query)

 

    keys & (1<<ord(arr[nx][ny])-ord('A'))

 

현재 키와 내가 확인하고 싶은 자리를 &(AND) 연산을 한다. 만약 해당 자리가 SET 되어있다면 0이 아닌 값을 얻게되고, 해당 자리가 SET 되어있지 않다면 0을 얻게된다.

 

그 이유는 우리가 확인하고 싶은 자리에 대한 이진수는 특정 자리 빼고는 모두 0인 이진수이다. 이를 비교대상과 &(AND) 연산을 하게 되면, 해당 자리가 1이 아니면 모두 0이되어 0을 리턴하게 된다. 이 원리는 활용한 것이다.

 

- 나머지는 일반 BFS의 흐름을 따른다.