백준 1194 파이썬 - 달이 차오른다, 가자.

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

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

문제

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

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

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

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

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

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

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

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

코드

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(n)]
dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
visited = [[[0] * 64 for _ in range(m)] for _ in range(n)]
def bfs():
    q = deque()
    one = [[i, j] for i in range(n) for j in range(m) if board[i][j] == '0']
    q.append((one[0][0], one[0][1], 0, 0))
    while q:
        x, y, d, a = q.popleft()
        for dx, dy in dr:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny][a] == 0:
                if board[nx][ny] == '1':
                    return d + 1
                elif board[nx][ny] == '.' or board[nx][ny] == '0':
                    visited[nx][ny][a] = 1
                    q.append((nx, ny, d + 1, a))
                elif board[nx][ny].islower():
                    na = a | (1 << ord(board[nx][ny]) - 97)
                    if visited[nx][ny][na] == 0:
                        visited[nx][ny][na] = 1
                        q.append((nx, ny, d + 1, na))
                elif board[nx][ny].isupper() and a & 1 << (ord(board[nx][ny]) - 65):
                    visited[nx][ny][a] = 1
                    q.append((nx, ny, d + 1, a))
    return -1
print(bfs())

풀이

bfs로 풀었고, a 변수가 핵심이다. a 가 000001이면 a키를 가지고 있고, 000101이면 a키와 c키를 가지고 있는 형식이다.

실패 코드

import sys
from collections import deque
from copy import deepcopy
n, m = map(int, sys.stdin.readline().split())
board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(n)]
dr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
def bfs():
    q = deque()
    one = [[i, j] for i in range(n) for j in range(m) if board[i][j] == '0']
    alpha = [0] * 6
    q.append((one[0][0], one[0][1], 0, alpha))
    while q:
        x, y, d, a = q.popleft()
        for dx, dy in dr:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < m:
                array = deepcopy(a)
                tmp = board[nx][ny]
                if tmp == '1':
                    return d + 1
                elif tmp == '.' or tmp == '0':
                    q.append((nx, ny, d + 1, array))
                elif tmp.islower():
                    if not array[ord(tmp) - ord('a')]:
                        array[ord(tmp) - ord('a')] = 1
                        q.append((nx, ny, d + 1, array))
                    else:
                        q.append((nx, ny, d + 1, array))
                elif tmp.isupper() and array[ord(tmp) - ord('A')]:
                    q.append((nx, ny, d + 1, array))
    return -1
print(bfs())

a를 배열로 넣었더니 실패했었다.