백준 1504번 : 특정한 최단 경로

2024.02.10 - [알고리즘] - 다익스트라 알고리즘

이 문제는 다익스트라 알고리즘을 활용하여 최단 경로를 찾는 문제입니다. 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단 거리를 찾을 때 사용되는 알고리즘으로, 가중치가 있는 그래프에서 음수 가중치가 없을 때 효율적으로 사용할 수 있습니다.

다익스트라 알고리즘의 개념

다익스트라 알고리즘의 핵심은 시작 정점에서 다른 정점들로 가는 최단 경로를 점진적으로 찾는 것입니다. 최단 거리를 기록하면서, 방문하지 않은 정점 중 현재까지 가장 짧은 거리로 도달할 수 있는 정점을 선택해 이동하며 최단 경로를 찾아나갑니다.

다익스트라 알고리즘의 동작 과정

1. 초기화: 시작 정점의 거리를 0으로 설정하고, 다른 모든 정점의 거리는 무한대로 초기화합니다.
2. 정점 선택: 방문하지 않은 정점들 중 최단 거리를 가진 정점을 선택합니다.
3. 거리 갱신: 현재 정점에서 인접한 다른 정점으로 이동하는 거리가 현재 저장된 거리보다 짧으면 거리를 갱신합니다.
4. 반복: 모든 정점이 방문될 때까지 위 과정을 반복하며 최단 거리를 찾아냅니다.

이 문제에서는 1번 정점에서 N번 정점까지 이동하되, 반드시 두 개의 특정 정점(v1, v2)을 거쳐야 한다는 조건이 있습니다. 이를 해결하기 위해 다익스트라 알고리즘을 여러 번 사용하여 총 두 가지 경로를 고려합니다.

 

1. 1번 정점에서 v1을 거쳐 v2를 지나 N번 정점으로 가는 경로
2. 1번 정점에서 v2를 거쳐 v1을 지나 N번 정점으로 가는 경로

이 두 경로의 거리 중 더 짧은 경로를 선택하는 방식으로 풀 수 있습니다. 각 경로에서 1번부터 v1, v2, N번까지의 최단 거리를 각각 계산해야 하므로, 세 번의 다익스트라 실행이 필요합니다.

import sys
import heapq

input=sys.stdin.readline

def dijkstra(graph,start):
    distance = [1e8 for i in range(n + 1)]
    queue=([(0,start)]) #시작노드거리 0, 시작 노드 1
    distance[start]=0
    while queue:
        current_distance,current_node=heapq.heappop(queue)
        if distance[current_node]<current_distance:
            continue

        for i in graph[current_node]:
            next_distance,next_node=i[1],i[0] #다음 노드거리, 다음노드

            if next_distance+distance[current_node]<distance[next_node]:
                distance[next_node]=next_distance+distance[current_node]
                heapq.heappush(queue,(distance[next_node],next_node))


    return distance


n,e=map(int,input().split())
graph=[[] for i in range(n+1)]


for i in range(e):
    #b:노드 c거리
    a,b,c=map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

v1,v2=map(int,input().split())
start_distacne=dijkstra(graph,1)
v1_distance=dijkstra(graph,v1)
v2_distance=dijkstra(graph,v2)


min_v1=start_distacne[v1]+v1_distance[v2]+v2_distance[n]
min_v2=start_distacne[v2]+v2_distance[v1]+v1_distance[n]
res=min(min_v1, min_v2)
print(res if res<1e8 else -1)