백준-1504-특정한 최단 경로

문제

특정한 최단 경로

풀이

1. 문제조건 해석

   특정 노드를 지나는 최단경로 문제

   노드 1에서 시작해서 노드 n까지 도착하는 최단경로 문제

   단, 문제에서 주어진 두 개의 노드를 꼭 지나가는 최단경로여야 한다.

2. 알고리즘

   • 다익스트라 알고리즘으로 해결하려고 시도했다.
   • 무방향 그래프(양방향 그래프)임에 주의
   • Optimal Substructure(최단 경로의 부분 경로는 또한 최단경로) 성질을 이용하면 지나가는 두 노드까지의 최단경로들의 합을 구하면 된다.
     • 시작노드 <-> 첫번째/두번쨰 노드
     • 첫번째 노드 <-> 두번째 노드
     • 두번째/첫번째 노드 <-> 마지막 노드 경로의 합
   • 우선순위 큐를 통해 거리가 짧은 노드부터 접근함에 유의
     • 큐에서 pop 된 노드는 해당 노드까지의 최단거리를 구한 상태이다.
     • 모든 노드까지가 아닌 특정 노드까지의 최단경로를 구할 때, 필요없는 연산을 줄일 수 있음
3. 코드

    from sys import stdin
    import heapq
    input = stdin.readline
    INF = 1000*800+1
   
    n, e = [int(x) for x in input().rstrip().split()]
    adj = [dict() for _ in range(n+1)]
    for _ in range(e):
        u, v, w = [int(x) for x in input().rstrip().split()]
        if v in adj[u] and adj[u][v] < w:
            pass
        else:
            adj[u][v] = w
        if u in adj[v] and adj[v][u] < w:
            pass
        else:
            adj[v][u] = w
           
    v1, v2 = [int(x) for x in input().rstrip().split()]
   
    def dijkstra(adj, start, goal):    
        '''
        특정 노드까지만 구하는 최적화 적용하지 않음
        '''
        dist = [INF for _ in range(len(adj))]
        pq = []
        dist[start] = 0
        heapq.heappush(pq, (dist[start], start))
   
        while pq:
            prev_dist, u = heapq.heappop(pq)
            if dist[u] < prev_dist:
                continue
            for v, w in adj[u].items():
                if dist[u]+w < dist[v]:
                    dist[v] = dist[u]+w
                    heapq.heappush(pq, (dist[v], v))
           
        return dist[goal]
   
    one = dijkstra(adj, 1, v1) + dijkstra(adj, v2, n)
    two = dijkstra(adj, 1, v2) + dijkstra(adj, v1, n)
    between = dijkstra(adj, v1, v2)
    if one >= INF and two >= INF:
        print(-1)
    elif one <= two:
        print(one+between)
    else:
        print(two+between)
   

    def dijkstra(adj, start, goal):
        '''
        특정 노드까지만 최단거리 구하는 최적화 수행
        '''
        dist = [INF for _ in range(len(adj))]
        pq = []
        dist[start] = 0
        heapq.heappush(pq, (dist[start], start))
   
        while pq:
            prev_dist, u = heapq.heappop(pq)
            # 모든 노드에 대해 최단경로 볼 필요 없다
            # 목표 노드에 대해서만 구하면 됨
            # 거리가 작은 순으로 탐색함에 주의
            if u == goal:
                return dist[goal]
            if dist[u] < prev_dist:
                continue
            for v, w in adj[u].items():
                if dist[u]+w < dist[v]:
                    dist[v] = dist[u]+w
                    heapq.heappush(pq, (dist[v], v))
        return dist[goal]
   

4. 배운점

   • 일반적인 다익스트라는 특정 노드에서 출발해 모든 노드까지의 최소경로 구한다
   • 특정 노드까지의 최소경로를 구할 때, 우선순위 큐의 성질을 이용하면 최적화할 수 있다.
   • 유사 문제
     • 4485-녹색 옷 입은 애가 젤다지?
     • 1753-최단경로