다익스트라 알고리즘 활용 문제 (프로그래머스 level 4 - 미로찾기)

level 4 - 미로찾기

https://school.programmers.co.kr/learn/courses/30/lessons/81304

프로그래머스

 

문제 자체가 다익스트라로 최적화 할 뿐 아니라 trap을 밟는경우 안밟는 경우를 나눠서 두개의 다익스트라를 만들어야 할 것 같다.

 

trap을 밟음으로 인해서 화살표가 반대방향으로 바뀌는 상황을 swap_graph 와 graph를 계속 교차하면서 참고하도록 구현했는데, 기존의 다익스트라 방법을 통해서는 swap을 통해서만 갈 수 있는 노드를 계산하지 못한다(왜? swap을 밟아야 도달가능한 경우, 이와 연결된 연결노드에 도달했을 때 다익스트라 최솟값을 갖는 경우가 아니기 때문에 탐색을 진행하지 않게 된다)

 

즉, 각 노드는, trap을 밟았을 때의 최솟값(활성화 됐을 때), trap을 밟지 않았을 때의 최솟값(트랩 비활성화) 의 최솟값을 모두 들고있어야 구현 가능하다.

 

 

+++

기존의 문제 해석을 단순히 trap의 on off 로서 생각을 했고, trap on 시에 전체 노드의 방향이 바뀌는줄 알았는데, 그게 아니라 연결노드만 바뀐다. 즉 문제 상황이 더 복잡해 질 수 있는데, 2개의 노드가 둘다 trap 상황이라면, 두개의 노드 각각이 켜져있는지 꺼져있는지 즉 2의 2승인 4가지의 경우 모두 다른 상황이 된다.

 

(질문하기)의 대부분 풀이 역시 각 트랩에 대한 visit를 만들고, 그 상황마다의 다익스트라 알고리즘으로 구한 최솟값을 모두 계산하는것으로 보여진다.(트랩이 최대 10개이므로 최대 경우의 수는 2의 10승인 1024)

 

 

 

 

기존 코드 (수정 필요)

import heapq
from collections import defaultdict
Inf = 100000


def solution(n, start, end, roads, traps):
    dij = [Inf for i in range(n+1)]          # 다익스트라 알고리즘
    dij_swap = [Inf for i in range(n+1)]
    dij[start] = 0                           # 시작값으로부터의 거리이므로 시작값에서의 초기 거리는 0
    queue = []                                   # 다익스트라 알고리즘으로 최소거리를 찾아나갈 때, 
    heapq.heappush(queue,[dij[start],start])     # 간선거리를 무작위로 받으면 최솟값 탐색이 느려짐. 개선하기 위해 힙을 사용 
    
    graph = defaultdict(list)              # graph[시작점] = [[도착점, 거리], ... ] 
    swap_graph = defaultdict(list)
    
    for p, q, s in roads :                 # graph dict, swap_graph dict 생성
        graph[p].append([q,s])
        swap_graph[q].append([p,s])
    
    trap_switch = False
    def traps_dij (traps, trap_switch, queue) :
        
        # 도착점이 traps 원소라면, 다익스트라 거리 계산 후에 trap_switch가 반대인 경우로 넘어가야함.
        
        if trap_switch :
            use_g = swap_graph
        else :
            use_g = graph
        
        while queue :
            cumsum_sec,p_room = heapq.heappop(queue)
            
            # 만약 이 길을 통해 온 노드까지의 시간이, 기존의 최소 시간보다 길면 더 볼필요가 없다
            if dij[p_room] < cumsum_sec :         
                continue
            
            for q, s in use_g[p_room] :
                new_sec = cumsum_sec + s
                if new_sec < dij[q] :
                    dij[q] = new_sec
                    if q not in traps :
                        heapq.heappush(queue,[dij[q],q])
                    else :
                        new_queue = []
                        heapq.heappush(new_queue,[dij[q],q])
                        new_trap_switch = not trap_switch
                        traps_dij (traps, new_trap_switch, new_queue) 
    
    traps_dij(traps, trap_switch, queue)
    
    return min(dij[end],dij_swap[end])