위 예시 그림은 카카오 미로 탈출의 초기 상태를 나타냅니다. 1번부터 3번까지 번호가 붙어있는 3개의 방이 있고, 방과 방 사이를 연결하는 길에는 이동하는데 걸리는 시간이 표시되어 있습니다. 길은 화살표가 가리키는 방향으로만 이동할 수 있습니다. 미로에는 함정이 존재하며, 함정으로 이동하면, 이동한 함정과 연결된 모든 화살표의 방향이 바뀝니다. 출발지점인 1번 방에서 탈출이 가능한 3번 방까지 이동해야 합니다. 탈출하는데 걸리는 최소 시간을 구하려고 합니다.
그림의 원은 방을 나타내며 원 안의 숫자는 방 번호를 나타냅니다.
방이 n개일 때, 방 번호는 1부터 n까지 사용됩니다.
화살표에 표시된 숫자는 방과 방 사이를 이동할 때 걸리는 시간을 나타냅니다.
화살표가 가리키고 있는 방향으로만 이동이 가능합니다. 즉, 위 그림에서 2번 방에서 1번 방으로는 이동할 수 없습니다.
그림에 표시된 빨간색 방인 2번 방은 함정입니다.
함정 방으로 이동하는 순간, 이동한 함정 방과 연결되어있는 모든 길의 방향이 반대가 됩니다.
위 그림 1번 방에서 2번 방으로 이동하는 순간 1에서 2로 이동할 수 있던 길은 2에서 1로 이동할 수 있는 길로 바뀌고, 3에서 2로 이동할 수 있던 길은 2에서 3으로 이동할 수 있는 길로 바뀝니다.
똑같은 함정 방을 두 번째 방문하게 되면 원래 방향의 길로 돌아옵니다. 즉, 여러 번 방문하여 계속 길의 방향을 반대로 뒤집을 수 있습니다.
미로를 탈출하는데 필요한 최단 시간은 다음과 같습니다.
1→2: 2번 방으로 이동합니다. 이동 시간은 2입니다.
함정 발동: 2번 방과 연결된 모든 길의 방향이 반대가 됩니다.
2→3: 3번 방으로 이동합니다. 이동 시간은 3입니다.
탈출에 성공했습니다. 총 이동시간은 5입니다.
방의 개수를 나타내는 정수 n, 출발 방의 번호 start, 도착 방의 번호 end, 통로와 이동시간을 나타내는 2차원 정수 배열 roads, 함정 방의 번호를 담은 정수 배열 traps이 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최단 시간을 return 하도록 solution 함수를 완성해주세요.
기본적으로 최소 길이 탐색이므로 heap을 이용한 다익스트라 알고리즘을 이용한다. traps의 최대 길이가 10이므로, traps의 방문을 저장하되 비트마스킹을 이용하면 된다. 각 함정 번호의 인덱스를 저장하고, 인덱스의 방문 여부를 1과 0으로 구분한다. 1은 그 트랩을 홀수 번 방문했다는 의미이며, 0은 짝수 번을 방문했다는 의미이다.
edge의 정보를 저장할때, 나가는 아웃코스와 들어오는 인코스를 저장한다. 인코스는 (Q, P, S)순으로 저장하면 간단하다.
함정 방의 방문 정보가 중요한 이유 : 아웃코스와 인코스를 구분하기 위해서이다. 함정 방에 방문하면 엣지의 방향이 바뀌므로(즉 그 노드와 인접한 인코스와 아웃코스 정보가 뒤바뀌므로) 각 함정 방을 홀수 번, 혹은 짝수 번 방문했는지의 여부가 중요하기 때문이다.
다음과 같은 상황이 있을 수 있다.
일반 노드 -> 일반 노드 : 일반적인 경우이므로 아웃코스만을 고려하면 된다.
일반 노드 -> 함정 노드 / 함정 노드 -> 함정 노드 / 함정 노드 -> 일반 노드 : 사실상 이 경우를 고려하기 위해서 비트마스킹을 고려하게 된다. 각 함정 노드를 방문한 총합이 홀수 번인지, 짝수 번인지에 따라 엣지의 방향이 결정되기 때문이다. 만약 총합이 짝수번이라면, 방향은 유지된다. (즉 아웃코스를 이용한다) 홀수 번이라면, 방향은 유지되지 않는다. (인코스를 이용한다)
또한, 총 방문 횟수를 저장하는 것은 매우 비효율적이다. 따라서 홀수 번 방문 여부를 저장하되, 그 인덱스에 대한 XOR연산을 이용할 수 있다. 홀수 및 짝수의 연산 결과의 진리표는 XOR 연산의 진리표와 동일하기 때문이다. 일반 노드는 방문하지 않은(0값인) 함정 노드로 간주할 수 있다. 아웃코스의 엣지에 대해, 만약 두 노드를 방문하지 않았거나, 두 노드를 방문하였다면 그 엣지를 이용할 수 있다. 인코스의 엣지에 대해선 나머지 경우(한 함정 노드만 방문하였을 때)에 한해 그 엣지를 이용할 수 있다.
만약 함정 방을 방문하게 된다면, 그 함정 방 인덱스에 대해 XOR 연산을 취해 줌으로써 함정 방의 방문 여부를 업데이트할 수 있다.
풀이 코드
from collections import defaultdict
from heapq import heappush, heappop
MAX = float('inf')
def solution(n, start, end, roads, traps):
in_road_dict = defaultdict(list)
out_road_dict = defaultdict(list)
max_traps = len(traps)
is_trapped = lambda x, trapped : x in traps and trapped | 1 << traps.index(x) == trapped
visited = [[MAX]*(1 << max_traps) for _ in range(n+1)]
visited[start][0] = 0
for P, Q, S in roads :
out_road_dict[P].append((Q, S))
in_road_dict[Q].append((P, S))
answer = MAX
q = [(0, 0, start)]
while q :
dist, trapped, node = heappop(q)
if node == end :
return dist
is_cur_trapped = is_trapped(node, trapped)
for next_node, next_dist in in_road_dict[node] :
is_next_trapped = is_trapped(next_node, trapped)
if is_cur_trapped ^ is_next_trapped :
next_trapped = trapped ^ (1 << traps.index(next_node)) if next_node in traps else trapped
if visited[next_node][next_trapped] > dist + next_dist :
visited[next_node][next_trapped] = dist + next_dist
heappush(q, (dist + next_dist, next_trapped, next_node))
for next_node, next_dist in out_road_dict[node] :
is_next_trapped = is_trapped(next_node, trapped)
if not is_cur_trapped ^ is_next_trapped :
next_trapped = trapped ^ (1 << traps.index(next_node)) if next_node in traps else trapped
if visited[next_node][next_trapped] > dist + next_dist :
visited[next_node][next_trapped] = dist + next_dist
heappush(q, (dist + next_dist, next_trapped, next_node))
return 0
