[BOJ][🟡1][백준#01194] 달이 차오른다, 가자.

문제 출처

BAEKJOON Online Judge #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
f0.F..1

출력

7

예제 2

입력

5 5
....1
#1###
.1.#0
....A
.1.#.

출력

-1

예제 3

입력

7 8
a#c#eF.1
.#.#.#..
.#B#D###
0....F.1
C#E#A###
.#.#.#..
d#f#bF.1

출력

55

예제 4

입력

3 4
1..0
###.
1...

출력

3

예제 5

입력

3 5
..0..
.###.
..1.A

출력

6

예제 6

입력

4 5
0....
.#B#A
.#.#.
b#a#1

출력

19

예제 7

입력

1 11
c.0.C.C.C.1

출력

12

예제 8

입력

3 6
###...
#0A.1a
###...

출력

-1

My Sol

from collections import deque

def main():
    def find_begin():
        for i in range(I):
            for j in range(J):
                if mat[i][j] =='0': return i, j

    def check_visits(visits, i, j):
        return visits | (2**(i*I+j))

    def check_has_key(C, keys):
        return keys & (2**(ord(C)-65))

    def register_key(c, keys):
        return keys | (2**(ord(c)-97))

    def bfs():
        Q = deque([(bi, bj, 0, 0, 0)])
        while Q:
            i, j, keys, visits, moves = Q.popleft()
            if keys in visit[i][j]: continue
            checked_visits = check_visits(visits, i, j)
            visit[i][j].add(keys)
            for di, dj in ((-1,0),(1,0),(0,1),(0,-1)):
                si, sj = i+di, j+dj
                if not (0<=si<I and 0<=sj<J): continue
                if mat[si][sj] =='0':
                    Q.append((si, sj, keys, checked_visits, moves+1))
                elif mat[si][sj] == '1': return moves+1
                elif mat[si][sj] == '#': continue
                elif mat[si][sj] == '.':
                    Q.append((si, sj, keys, checked_visits, moves+1))
                else:
                    if mat[si][sj].isupper():
                        if not check_has_key(mat[si][sj], keys): continue
                        Q.append((si, sj, keys, checked_visits, moves+1))
                    else:
                        new_keys = register_key(mat[si][sj], keys)
                        Q.append((si, sj, new_keys, checked_visits, moves+1))

        return -1

    I, J = map(int, input().split())
    mat = [list(input()) for _ in range(I)]
    bi, bj = find_begin()
    visit = [[set() for _ in range(J)] for _ in range(I)]
    return bfs()

print(main())

비트마스킹과 BFS를 활용하여 해결하는 문제였다. 열쇠, 그리고 각 경우마다 visited를 비트마스킹으로 저장해 Queue에 넣었다.

1. 가로세로 길이와 격자를 input으로 받아 저장한다.
2. find_begin 함수를 통해 0의 좌표를 찾아 저장한다.
3. 2차원 배열 visit을 초기화한다. 비트마스킹 처리한 key를 각 set에 추가하는데, 이때 같은 key를 들고 재방문한다면 이후 이동을 안하는 방식으로 visit을 활용하였다.
4. BFS를 시작한다. deque에 들어가는 각 요소는 좌표(i, j), 비트마스킹한 열쇠들(keys)과 방문했던 곳(visits), 그리고 이동 횟수(moves)를 저장한다.
5. visit 2차원 배열의 현재 좌표에 현재 keys를 들고 방문한 적이 있으면 넘어가고, 아니라면 keys를 등록한다. 이를 check_visits 함수를 통해 구현했다.
6. 현 좌표에서 사방을 확인하였는데, 만약 확인하는 좌표(si, sj)의 값이 1이라면 탈출이므로 현재까지의 이동 횟수(moves)에 1을 더해 return했다. #은 지나갈 수 없기 때문에 넘어갔고, 만약 0이나 .라면 그냥 지나갈 수 있도록 했다. 막히거나 확인할 것이 없는 지역이기 때문이다.
7. 이외의 경우에는 알파벳, 즉 열쇠나 문이므로 대소문자를 구분해 분기처리했다. 만약 대문자를 마주한다면, 현재 해당하는 대문자의 소문자가 키를 가지고 있는지를 체크했다. 이를 check_has_key 함수로 구현했으며, keys 자체가 비트마스킹 처리되어있으므로 마찬가지로 비트 방식으로 확인했다. key가 있는 경우에만 deque에 다음 이동을 추가하면 되었다.
8. 만약 소문자를 마주한다면, 현재 keys에 해당 알파벳의 key를 추가했다. 이를 register_key로 구현했으며 마찬가지로 비트 방식으로 추가했다. 그리고 다음 이동을 추가하면 되었다.

결과

맞았습니다!!