[Python/파이썬] 백준 1194번 달이 차오른다, 가자.

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

코드

from collections import deque

n, m = map(int, input().split())
maze = []
start = []
for i in range(n):
    line = list(input())
    for j in range(m):
        if line[j] == "0":
            start = [i, j]
            line[j] = "."
    maze.append(line)

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

q = deque([[*start, 0, frozenset()]])
visited = set()

while q:
    x, y, d, keys = q.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            new_keys = keys
            can_move = False
            if maze[nx][ny] == ".":  # 빈 칸
                can_move = True
            elif maze[nx][ny].isalpha() and maze[nx][ny].islower():  # 열쇠 획득
                new_keys = keys | {maze[nx][ny]}
                can_move = True
            elif maze[nx][ny].isalpha() and maze[nx][ny].isupper() and maze[nx][ny].lower() in keys:    # 문 열고 이동
                can_move = True
            elif maze[nx][ny] == "1":
                print(d+1)
                exit()

            if can_move and (nx, ny, new_keys) not in visited:
                q.append([nx, ny, d+1, new_keys])
                visited.add((nx, ny, new_keys))

print(-1)

 

모든 이동이 갖는 가중치가 같았기에 BFS를 사용해야 하는 문제였다. 다만, 주의해야 할 점은 일반적인 BFS와 다르게, 한 번 방문한 점이라도 키를 이전보다 더 갖고 오는 경우에는 다시 방문이 가능해야 한다는 점이다.

 

예를 들어, 1번째 테스트 케이스에서도 출발점에서 (0, 0)으로 가서 "f" 열쇠를 갖고 다시 출발점을 지나서 "F"문을 열고 지나가야 한다. 이런 경우들이 있을 수 있기 때문에 방문 처리를 할 때, 단순히 그 칸에 이전에 방문했는지 여부만 저장하면 안된다.

 

나는 방문 처리를 할 때, 칸 위치 정보와 더불어 가진 열쇠의 상태도 처리하도록 구현했다. 민식이가 소유한 열쇠 뭉치는 집합으로 표현했다. 이 때, 중간에 keys는 수정할 수 없는 집합인 `frozenset`에 넣어서 중간에 처리하며 값이 왜곡되는 것을 막았다.

 

---

 사실 민식이가 소유한 열쇠들을 집합이 아닌 비트마스킹을 이용해서 나타낼 수도 있다. "a"는 0번째 자리수, "b"는 1번째 자리수 이런식으로 말이다. 근데 이렇게 하려면 알파벳을 ASCII 코드로 변경해서 값을 계산하는 과정이 추가되어야 한다.