개요
🖱️ 문제 링크 : https://www.acmicpc.net/problem/1194
- 시간 제한 : 2초
- 메모리 제한 : 128 MB
문제
⌨️ 입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50)
둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다.
'0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.
🖨️ 출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다.
만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
해결 방법
💡 문제 이해
이런 미로 유형의 문제들이 풀이가 다 비슷비슷해가지고, 너무 익숙하게 대했다가 스스로 못 푼 문제다.
열쇠 칸을 만나면 set에 담아두었다가 (어자피 set는 중복을 제거해주니까 시간복잡도도 준수하고 이상할게 없었음), 문 칸을 만났을 때 해당 열쇠가 set에 있다면 진입 하는, 그런 로직으로 풀어보려고 했는데 말도 안되는 값이 출력됐다.
나중에 AC받은 코드 구글링해서 찾아보니까 필요한 열쇠가 흩어져 있을 수도 있어서, 방문했던 정점을 다시 방문 할 수 있어야 된단다. 그치만? 무조건 방문을 허용하지는 않고! (시간초과 너무해) 그래서 핵심은 다음과 같다.
현재 가지고 있는 열쇠 목록이 해당 정점을 방문하던 당시 열쇠목록과 다를 때만, 방문을 허용한다.
이게 뭔 개소린가 싶었는데 비트마스킹 어쩌고로 손쉽게 해결이 가능하단다.
📖 비트마스킹?
비트 마스킹을 설명하기에 앞서 기본 비트 연산자 부터 알고가자!
AND, OR, XOR
- AND 연산 (&): 대응하는 두 비트가 모두 1일 때, 1 반환
- OR 연산 (|): 대응하는 두 비트가 하나라도 1일 때, 1 반환
- XOR 연산 (^): 대응하는 두 비트가 서로 다르면, 1 반환
1010 & 1111 = 1010
1010 | 1111 = 1111
1010 ^ 1111 = 0101NOT
- NOT 연산 (~): 비트의 값을 반전하여 반환
~1010 = 0101왼쪽, 오른쪽 Shift
- 왼쪽 Shift (<<): 왼쪽으로 비트를 옮긴다. (A * 2^B) 의미
- 오른쪽 Shift (>>): 오른쪽으로 비트를 옮긴다. (A / 2^B) 의미
00001010 << 2 = 101000
00001010 >> 2 = 000010를 이용해서 비트마스크 테크닉을 쓴다 카더라.
비트 마스크란? 우선, 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라 한다.
컴퓨터는 내부적으로 bit 단위로 연산을 한다. bit는 모두 익히 알 듯이 0과 1로만 이루어져 있는데 이 특징을 이용해서 다양한 알고리즘 문제에서 간결한 코드와 빠른 속도로 활용이 가능하다.
가령, 10개의 방문을 체크해야 한다면 보통 check = [False] * 10와 같이 리스트를 많이 사용한다. 비트 마스킹은 아래와 같이 표현해서 하위 주소인 오른쪽부터 0인지 1인지 확인하면 된다.
check = 0b0000000000열쇠가 'a' ~ 'f' 까지 총 6개이므로, 총 경우의 수는 2^6 = 64가지 이다.
visited = [[[-1] * (1 << 6) for _ in range(M)] for _ in range(N)]미로의 가로 X 미로의 세로 X 열쇠의 경우의 수 까지 해서 3차원 배열으로 방문처리 리스트를 짰다. 이렇게 코드 작성시 새로운 열쇠를 획득 했을 때 key 값이 변하므로 이미 방문했던 정점을 다시 방문 할 수 있게 된다.
즉, 좌표 이동시 [x][y][key] 에 접근하여 그 값이 -1이면 동일한 키를 가지고 그곳에 방문하지 않았다는 뜻이 된다.
Python Code
# 백준 1194 달이 차오른다, 가자
# 비트 마스크
import sys
from collections import deque
read = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def haveKey(cur_key, door):
# and 연산 결과 거짓이면 0을 리턴함.
value = cur_key & (1 << (ord(door) - ord('A')))
return True if value else False
def BFS(x,y):
# 초기 상태는 x,y 좌표와 키를 하나도 가지고 있지 않으므로 0을 담아줌
queue = deque()
queue.append([x,y,0])
visited = [[[-1] * (1 << 6) for _ in range(M)] for _ in range(N)]
visited[x][y][0] = 0
while queue:
x,y,key = queue.popleft()
# 출구에 도착하면 최소 비용 리턴
if maze[x][y] == '1':
return visited[x][y][key]
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < M and visited[nx][ny][key] == -1:
# 방문한 지역이 빈칸이거나 출구 도달시
if maze[nx][ny] == '.' or maze[nx][ny] == '1':
visited[nx][ny][key] = visited[x][y][key] + 1
queue.append([nx,ny,key])
# 열쇠가 있는 칸에 방문
elif 'a' <= maze[nx][ny] <= 'f':
temp = key | (1 << (ord(maze[nx][ny]) - ord('a')))
visited[nx][ny][temp] = visited[x][y][key] + 1
queue.append([nx,ny,temp])
# 문이 있는 칸에 방문
elif 'A' <= maze[nx][ny] <= 'F':
# 키를 가지고 있다면
if haveKey(key, maze[nx][ny]):
visited[nx][ny][key] = visited[x][y][key] + 1
queue.append([nx,ny,key])
# 다 돌았는데 출구에 도달하지 못한다면
return -1
# 미로의 세로, 가로 크기
N,M = map(int,read().split())
maze = [ list(map(str,read().rstrip())) for _ in range(N) ]
for i in range(N):
for j in range(M):
# 민식이의 초기 위치
if maze[i][j] == '0':
start_x, start_y = i,j
maze[i][j] = '.'
print(BFS(start_x,start_y))
왜 못풀었는가?
애초에 비트마스크라는 개념도 몰랐기 때문에 못푸는게 정상이 아닌가 라고 자기합리화를 했다. 구글링 열심히 하면서 비트마스크 안쓴 풀이를 찾아보려고 했는데 전부다 이 테크닉으로 문제를 풀어서 결국 새롭게 공부했다.
방문 당시 가졌던 동일한 키를 가지고 그곳에 다시 방문하지 않아야 된다.
를 생각하는 것이 힘들었다. 당연히 방문했던 곳이니까 다시 방문 할 필요가 없다고 생각했는데 재 방문해야 더 짧은 최단거리가 나올 수 있다는 것을 알았다.
이 문제가 왜 골드 1일까라고 생각한 내가 조금 한심해졌다. 어렵다 어려워..
0개의 댓글
