문제 바로가기
문제:
지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다. 민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다. 하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다. 영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다. 민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다
빈 칸: 언제나 이동할 수 있다. ('.')
벽: 절대 이동할 수 없다. ('#')
열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('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를 이용한 풀이이다.
비트마스킹을 잘 몰랐기 때문에 일단 비트마스킹을 먼저 공부하고 들어갔다.
간단히 하면
& 는 And연산자이고 | 는 or연산자이다.
즉 이 문제에서 확인해보면 문을 만났을때 키와, 문을 & 연산자로 했을때 1이 나오는지 확인하면된다.
키를 만나면 키를 먹어야 하기 때문에 OR 연산자인 | 을 해주면 된다.
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m = map(int, sys.stdin.readline().split(" "))
graph = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(n)]
visited = [[[False] * m for _ in range(n)] for _ in range(64)]
# 이동방향
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 시작 좌표
Q = deque()
for x in range(n):
for y in range(m):
if graph[x][y] == "0":
Q.append((x, y, 0, 0)) # x, y 좌표 이동수, 키 상태
graph[x][y] = "."
while Q:
x, y, move_count, key_list = Q.popleft()
visited[0][x][y] = True
for dx, dy in move:
nx = dx + x
ny = dy + y
# 범위 안,
if 0 <= nx < n and 0 <= ny < m and not visited[key_list][nx][ny]:
# 도착
print(nx, ny,key_list)
if graph[nx][ny] == "1":
print(move_count + 1)
exit()
# 그냥 지나갈수 있음
elif graph[nx][ny] == ".":
visited[key_list][nx][ny] = True
Q.append((nx, ny, move_count + 1, key_list))
# key를 만나면 챙겨야지
elif graph[nx][ny] in ['a', 'b', 'c', 'd', 'e', 'f']:
# 키 의 값을 알게됨 d 면 왼쪽 3 칸 밀어야지요
n_key = key_list | (1 << (ord(graph[nx][ny]) - ord('a')))
visited[n_key][nx][ny] = True
Q.append((nx, ny, move_count + 1, n_key))
# 문이면? 키 있는지 체크 >> 비트마스킹으로 체킹
elif graph[nx][ny] in ['A', 'B', 'C', 'D', 'E', 'F']:
# 둘다 있음
if key_list & (1 << (ord(graph[nx][ny]) - ord('A'))):
visited[key_list][nx][ny] = True
Q.append((nx, ny, move_count + 1, key_list))
print(-1)
# 문을 만나면 & 로 체크
# 키를 만나면 | 로 두개 다 챙김
Q에 들어가는 값은 시작 위치와, 움직인 횟수, 현재 있는 들고 있는 키이다.
1 7
f0.F..1
visited 의 마지막 range가 64인이유는 키의 갯수가 6개이다. 2^6 은 64 이기때문에
키를 가지는 경우의수가 64개 이기때문에 그만큼 다 들고있는 것이다.
댓글