[백준/BOJ] gold1 - 1194번 달이 차오른다, 가자. (Python)

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

 

▶풀이

bfs를 이용해서 푸는 문제입니다.

일반적인 bfs랑은 조금 다른 게 벽만 있는 게 아니라 문을 통과하기 위해서 열쇠도 있어야 합니다.

그래서 열쇠의 유무를 판단하기 위해서 key값도 함께 넣어서 풀었습니다

 

열쇠 a가 있으면 key값은 1

열쇠 b가 있으면 key값은 2

열쇠 c가 있으면 key 값은 4

 

이렇게 이진법을 이용해서 key값에 추가해주어 문을 통과할 수 있는지 없는지를 확인했습니다.

나머지는 일반적은 bfs와 같은 방식으로 풀었습니다.

 

from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs():
    while que:
        x, y, key, cnt = que.popleft()
        for i in range(4):
            x1 = x + dx[i]
            y1 = y + dy[i]

            if 0 <= x1 < n and 0 <= y1 < m and Map[x1][y1] != '#' and visit[x1][y1][key] == 0:
                if Map[x1][y1] == '1':
                    return cnt + 1
                elif Map[x1][y1] == '.':
                    visit[x1][y1][key] = 1
                    que.append([x1, y1, key, cnt+1])
                else:
                    if Map[x1][y1].isupper():
                        keychar = ord(Map[x1][y1]) - 65
                        if key & 1 << keychar:
                            visit[x1][y1][key] = 1
                            que.append([x1, y1, key, cnt+1])
                    elif Map[x1][y1].islower():
                        keychar = ord(Map[x1][y1]) - 97
                        sumkey = key | (1 << keychar)
                        if visit[x1][y1][sumkey] == 0:
                            visit[x1][y1][sumkey] = 1
                            que.append([x1, y1, sumkey, cnt+1])
    return -1


n, m = map(int, input().split())
visit = [[[0] * 64 for i in range(m)] for i in range(n)]
que = deque()
Map = []

for i in range(n):
    Map.append(list(input().strip()))
    for j in range(m):
        if Map[i][j] == '0':
            que.append([i, j, 0, 0])
            Map[i][j] = '.'
            visit[i][j][0] = 1
print(bfs())