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

문제 소개 🧐

방향성이 없는 그래프에서, 반드시 거쳐야 하는 두 정점을 포함하여 1번 정점에서 N번 정점까지 가는 최단 경로의 길이를 찾는 문제이다.

입력 📝

  • 첫째 줄에 정점의 개수 N(2 ≤ N ≤ 800)과 간선의 개수 E(0 ≤ E ≤ 200,000)가 주어진다.
  • E개의 줄에 걸쳐 간선 정보 a, b와 거리 c(1 ≤ c ≤ 1,000)가 주어진다.
  • 마지막 줄에 반드시 거쳐야 하는 두 정점 v1, v2가 주어진다.

출력 📤

  • 1번 정점에서 N번 정점까지 두 정점을 모두 거치는 최단 경로의 길이를 출력한다.
  • 경로가 없는 경우에는 -1을 출력한다.

제한 ❌

  • v1 ≠ v2, v1 ≠ N, v2 ≠ 1
  • 한번 이동했던 정점과 간선도 다시 이동할 수 있다.

첫 번째 시도: 다익스트라 ✨

Idea

가중치가 모두 양수인 방향 없는 그래프이므로, 최단 경로를 찾는 데 다익스트라 알고리즘을 사용하는 것이 자연스럽다.

반드시 v1과 v2를 거쳐야 하므로, 1번에서 N번으로 가는 경로는 다음 두 가지 경우로 압축할 수 있다.

  1. 1 → v1 → v2 → N
  2. 1 → v2 → v1 → N

이 두 경로의 길이를 각각 계산한 뒤, 더 작은 값을 최종 답으로 선택하면 된다.
각 구간의 최단 거리는 다익스트라 알고리즘으로 구할 수 있다.

  • 경로 1의 총 거리 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
  • 경로 2의 총 거리 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)

dijkstra(start, end)는 start 정점에서 end 정점까지의 최단 거리를 의미한다.
v1과 v2 사이의 거리는 양방향이므로 dijkstra(v1, v2)와 dijkstra(v2, v1)은 같다.

따라서 다익스트라 함수를 총 3번 호출하여 필요한 모든 값을 얻을 수 있다.

  1. 출발점이 1일 때
  2. 출발점이 v1일 때
  3. 출발점이 v2일 때

만약 두 경로 중 하나라도 중간에 연결되지 않는 구간이 있다면 해당 경로의 길이는 무한대(infinity)가 될 것이고, 두 경로 모두 불가능하다면 최종 결과는 무한대가 되므로 -1을 출력한다.

Code

import sys
import heapq

N, E = map(int, sys.stdin.readline().split())

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

for i in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((c,b))
    graph[b].append((c,a))

v1, v2 = map(int, sys.stdin.readline().split())

def dijkstra(start, graph, trg):
    global N
    q = []
    q.append(start)
    path = [float('inf')] * (N+1)
    path[start[1]] = start[0]

    while q:
        w, v = heapq.heappop(q)

        if path[v] < w:
            continue

        for n_w, n_v in graph[v]:
            sum_w = w + n_w

            if path[n_v] > sum_w:
                path[n_v] = sum_w
                heapq.heappush(q, (sum_w, n_v))
    return path[trg]

v1_v2_dis = dijkstra((0,v1), graph, v2)
answer = min((dijkstra((0, 1), graph, v1) + v1_v2_dis + dijkstra((0,v2), graph, N)), 
                (dijkstra((0, 1), graph, v2) + v1_v2_dis + dijkstra((0,v1), graph, N)))

print(answer) if answer != float('inf') else print(-1)

Result

  • 성공! 🎉
  • 주어진 아이디어대로 두 가지 경로(1->v1->v2->N, 1->v2->v1->N)의 최단 거리를 각각 계산하고 비교하는 로직이 유효했다.

개선할 부분 🤔

  • 현재 코드는 기능적으로 완벽하게 동작한다.
  • 다만, answer를 계산하는 마지막 줄이 다소 길어 가독성이 떨어질 수 있다. 각 경로(path1, path2)의 계산을 별도의 변수로 분리하면 코드를 이해하기 더 쉬워질 것이다.
  • 이 문제는 최단 경로 문제의 응용으로, ‘반드시 거쳐야 할 경유지가 있는 경우 어떻게 경로를 분할하여 생각할 것인가’ 에 대한 좋은 연습이 되었다.
⁂