문제
https://www.acmicpc.net/problem/1194
접근방식
✨ BFS & 비트마스킹 활용
👉 비트마스킹
사실 비트마스킹 말만 들어봤지, 사용해본 적은 없었는데
이 문제는 도무지 각이 안 잡혀서 다른 풀이들을 참고하다가.. 비트마스킹 아니면 안되겠다 싶었다.
❔ 내가 이해한 비트마스킹을 간단히 정리해보자면
이진수의 특성을 영리하게 활용한 기법이다.
하나의 자리가 0/1 -> false/true 상태를 표현할 수 있다는 특성을 활용해, 조합에 따른 상태값을 구분할 수 있다.
예를 들어, 총 다섯 가지 원소를 가진 {1, 2, 3, 4, 5}는 아래와 같은 조합일 수 있다.
- {1, 2, 3, 4} => 11110
- {1, 4, 5} => 10011
- {3} => 100비트마스킹을 통해 늘상 활용하는 배열이 아닌(ex. check = [False] * 5), 하나의 숫자만으로 공간 효율적으로 상태값을 표현할 수 있다.
👉 그럼 문제에 적용해보자
동작을 정리하자면;
- 만약 현재의 키 조합으로 간 곳이 아니라면, 이동 가능성이 있음. 다만, 어떤 칸이냐에 따라 동작을 달리 한다
1) key가 있는 칸에 간다면, key 조합을 갱신하기
2) door가 있는 칸에 간다면, 현재의 key 조합으로 문을 열 수 있는지 볼 것 -> 문을 열 수 없다면, 이동할 수 없음✅ 방문 여부 표시
이 문제에서의 관건은 갔던 데를 또 갈 수 있다는 건 확실한데 .. 무슨 기준으로 허용할까?
동일한 키 조합으로 방문한 적이 없는지를 볼 필요가 있고, 이건 'a' ~ 'f'의 키를 가졌냐 안 가졌냐를 000000 ~ 111111 로 표현할 수 있다는 걸 활용할 수 있다. (조합에 따라 총 64가지의 상태값을 가질 것이다)
그러므로 visited 자료구조는 다음과 같이 표현할 수 있다:
# 해당 키 조합으로 (x, y)에 방문한 적이 있는가 ?
visited = [[[False] * (1 << 6) for _ in range(m)] for _ in range(n)]✅ key인 경우, 현재 키 조합 갱신하기
현재 키 조합인 ck와 maze의 key로 키 조합을 갱신하려면 어떻게 할까?
OR 연산을 활용할 수 있다. 둘 중 하나만 참이면 참이라는 연산의 특성을 활용하면, 새로운 키를 갱신할 수 있다.
nk = ck | 1 << (ord(maze[cx + dx][cy + dy]) - ord('a')){f, e, d, c, b, a} 조합을 xxxxxx라는 상태값으로 표현한다면, shift 연산을 활용해서 새로운 키 조합을 갱신할 수 있을 것이다.
✅ door인 경우, 현재 키 조합으로 문을 열 수 있는가 ?
door의 값과 현재 key 조합에서 해당 알파벳이 존재하면 된다.
AND 연산을 통해 둘다 있는 경우를 보장할 수 있다:
ck & 1 << (ord(maze[cx + dx][cy + dy]) - ord('A'))
-> 1인 경우 문을 열 수 있음코드
from collections import deque
def bfs():
visited = [[[False] * (1 << 6) for _ in range(m)] for _ in range(n)]
queue = deque([(sx, sy, 0, 0)]) # (현 위치 xy, 현 key 조합(누적), 거리 d)
visited[sx][sy][0] = True
while queue:
cx, cy, ck, cd = queue.popleft()
if maze[cx][cy] == '1':
return cd # 최단 경로 반환
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
if 0 <= cx + dx < n and 0 <= cy + dy < m and not visited[cx + dx][cy + dy][ck] and maze[cx + dx][cy + dy] != '#':
nk = ck # 새로운 키 조합
# key
if 'a' <= maze[cx + dx][cy + dy] <= 'f':
nk = ck | 1 << (ord(maze[cx + dx][cy + dy]) - ord('a')) # 키 조합 갱신
# door
elif 'A' <= maze[cx + dx][cy + dy] <= 'F':
# 열 수 없으면 PASS
if not (ck & 1 << (ord(maze[cx + dx][cy + dy]) - ord('A'))):
continue
visited[cx + dx][cy + dy][nk] = True
queue.append((cx + dx, cy + dy, nk, cd + 1))
return -1 # 탈출 불가
n, m = map(int, input().split())
maze = []
for _ in range(n):
maze.append(input())
# 시작점 찾기
sx, sy = None, None
for i in range(n):
maze[i] = list(maze[i])
for j in range(m):
if maze[i][j] == '0':
sx, sy = i, j
break
print(bfs())