====== 미로 탈출 ======

===== 풀이 =====
  * 양수 가중치 그래프에서 최단 거리 경로를 찾는 문제이므로 다익스트라 알고리즘을 쓰면 된다.
  * 다만 트랩의 상태에 따라서 그래프가 바뀌는 것이 문제인데, 무식해보이지만 단순한 방법은 노드와 트랩 상태를 묶은 것을 새로운 노드로 정의하고, 그러한 노드들을 가지고 그래프를 새로 만드는 것이다.
  * 트랩의 갯수는 최대 10개이므로, 트랩의 상태는 최대 2^10가지. 원래 노드의 갯수는 V≤1000이었으므로, 노드와 트랩 상태를 묶어서 새로운 노드들을 만들더라도 새로이 만들어지는 노드들의 갯수는 최대 1000*2^10 이다. 엣지의 갯수도 원래 엣지의 갯수가 E≤3000 이었으므로, 새 그래프에서의 엣지 수는 최대 3000*2^10 이다. 이대로 다익스트라를 돌리면 다익스트라의 시간복잡도가 O(ElogV)이므로 대충 3*10^6*20 정도니까 시간 내에 못돌아갈 정도는 아니다.
  * 구현할때는 트랩들의 상태를 비트마스크로 표현하는 것이 편리하다. 어떤 상태노드에서 다른상태로들로 연결된 엣지 목록을 찾는 것은.. 실제로 각 상태별로 엣지들을 다 계산해서 그래프를 만들어주는 것은 너무 비효율적이고, 원본 그래프에서 노드 사이의 엣지들 목록과 현재의 트랩 상태를 이용해서 그때그때 계산해주면 된다. 원본 그래프에서 각 노드에 대한 in-edge와 out-edge를 모두 저장해둔 다음, 그중에서 현재 상태에서 실제로 out-edge가 되는것들을 분류해주면 된다.
  * 총 시간 복잡도는 앞에서 설명한대로, %%O((E*2^T)*log(V*2^T)) = O(E*T*2^T*logV)%%
  

===== 코드 =====
<dkpr py>
"""Solution code for "Programmers 81304. 미로 탈출".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/81304
- Solution link: http://www.teferi.net/ps/problems/programmers/81304
"""

import heapq

INF = float('inf')


def dijkstra(next_states_and_dists,
             source: int,
             is_sink_state) -> float:
    distances = {source: 0}
    heap = [(0, source)]
    while heap:
        dist_u, u = heapq.heappop(heap)
        if dist_u != distances[u]:
            continue
        if is_sink_state(u):
            return dist_u
        for v, dist_uv in next_states_and_dists(u):
            dist_v = dist_u + dist_uv
            if dist_v < distances.get(v, INF):
                distances[v] = dist_v
                heapq.heappush(heap, (dist_v, v))
    raise ValueError


def solution(n, start, end, roads, traps):
    def is_trap_activated(trap_state, node):
        return node in trap_bit and (trap_state & trap_bit[node]) != 0

    def flip_trap(trap_state, node):
        return (trap_state ^ trap_bit[node]) if node in trap_bit else trap_state

    def next_states_and_dists(state):
        u, trap_state = state
        is_cur_node_activated = is_trap_activated(trap_state, u)
        for v, dist in edges_from[u]:
            if is_cur_node_activated == is_trap_activated(trap_state, v):
                yield (v, flip_trap(trap_state, v)), dist
        for v, dist in edges_to[u]:
            if is_cur_node_activated != is_trap_activated(trap_state, v):
                yield (v, flip_trap(trap_state, v)), dist

    trap_bit = {trap - 1: (1 << i) for i, trap in enumerate(traps)}                
    edges_from = [[] for _ in range(n)]
    edges_to = [[] for _ in range(n)]    
    for u, v, dist in roads:
        edges_from[u - 1].append((v - 1, dist))
        edges_to[v - 1].append((u - 1, dist))

    return dijkstra(next_states_and_dists,
                    (start - 1, 0),
                    lambda state: state[0] == end - 1)
</dkpr>

{{tag>프로그래머스 ps:problems:programmers:Level_4}}