알고리즘 스터디 - 백준 1504번 : 특정한 최단 경로

문제 해석

• 방향이 없는 그래프로 1번 정점에서 N번 정점까지의 최단 경로
• 최단 경로를 움직이는데 임의의 두 정점은 반드시 통과해야한다.

어떤 알고리즘을 사용해야할까?

1. 정점의 개수 n, 간선의 개수 e
2. a, b, c : (a와 b 사이 간선의 길이가 c)
3. v1, v2를 지나야 함

알고리즘 코드

import heapq
import math

n, e = map(int, input().split())

graph = [[] for _ in range(n+1)]

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

def dijkstra(start):
    distance = [INF] * (n+1)
    distance[start] = 0
    queue = []
    heapq.heappush(queue, (distance[start], start))
    
    while queue:
        dist, node = heapq.heappop(queue)

        if distance[node] < dist:
            continue

        for next in graph[node]:
            weighted_distance = dist + next[1]
            if weighted_distance < distance[next[0]]:
                distance[next[0]] = weighted_distance
                heapq.heappush(queue, (weighted_distance, next[0]))
    
    return distance

v1, v2 = map(int, input().split())

INF = float('inf')

one_dist = dijkstra(1)
v1_dist = dijkstra(v1)
v2_dist = dijkstra(v2)

total_path1 = one_dist[v1] + v1_dist[v2] + v2_dist[n]
total_path2 = one_dist[v2] + v2_dist[v1] + v1_dist[n]

final = min(total_path1, total_path2)

if final < INF:
    print(final)
else:
    print(-1)

주의할 점

1. 서로 다른 케이스의 길이를 비교해야한다

1 -> v1 -> v2 -> n : 이런 식으로 될 수 있지만 다른 경우도 있기 때문이다.
1 -> v2 -> v1 -> n : 이 경우도 된다.

2. 그래프가 양방향인데 입력 설정을 잘못하면 런타임 에러가 생긴다

graph[a].append((b, c))
graph[b].append((a, c))

양방향이므로 2개로 설정해주기