[Python] 1504 - 특정한 최단 경로

[Gold IV] 특정한 최단 경로 - 1504 

[문제 링크](https://www.acmicpc.net/problem/1504)

🗝️알고리즘 분류

• 그래프 탐색
• 다익스트라
• 최단 경로

---

💻문제 정의

무방향 그래프가 주어졌을 때, 1에서 N까지의 경로 중, v1과 v2를 반드시 거치는 최단 경로를 구하는 문제이다.

 

💡접근 및 설계

다익스트라 최단 경로 알고리즘을 활용하였다.

 

1에서 v1까지의 최단경로, v1에서 v2의 최단경로, v2에서 N까지의 최단경로를 각각 구하여 합한것이 최단 경로가 될 것이다.

 

✏️알고리즘 풀이

def dijkstra(num, end):
    weight = [INF] * (N+1)

    queue = []
    heapq.heappush(queue, (0, num)) # 시작 위치의 가중치는 0

    weight[num] = 0

    while queue:
        wgt, now = heapq.heappop(queue) # 큐에 저장된 가중치와 정점 정보 pop

        if (weight[now] < wgt): # 현재 정점에 저장된 가중치가 더 작다 => 이미 작은 가중치로 현재 정점에 도착함
            continue

        for v, w in graph[now]:
            cost = wgt + w # 비용 = v로 가는데 드는 가중치 + 현재의 가중치
            if (cost < weight[v]): # 비용이 더 적게 들면
                weight[v] = cost # 더 작은 가중치로 변경
                heapq.heappush(queue, (cost, v)) # 힙에 푸쉬

    return weight[end]

두 점을 입력받으면, num에 대해 end까지의 최단 경로를 반환하는 dijkstra 함수이다.

 

가중치를 기준으로 최소 heap에 저장되어 최단 경로를 반환하는 방식이다.

 

v1, v2 = map(int, input().split())
result = min(dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N), dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N))
print(result if result < INF else -1)

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

 

두 개의 경로를 탐색하여 최솟값을 반환한다.

이때 result가 INF 값 이상이라면 어느 한 구간의 경로가 존재하지 않는다는 뜻이므로 -1을 출력한다.

 

 

🗒️제출 코드

# 1504 특정한 최단 경로

import heapq

INF = 1_000_000_000

def dijkstra(num, end):
    weight = [INF] * (N+1)

    queue = []
    heapq.heappush(queue, (0, num)) # 시작 위치의 가중치는 0

    weight[num] = 0

    while queue:
        wgt, now = heapq.heappop(queue) # 큐에 저장된 가중치와 정점 정보 pop

        if (weight[now] < wgt): # 현재 정점에 저장된 가중치가 더 작다 => 이미 작은 가중치로 현재 정점에 도착함
            continue

        for v, w in graph[now]:
            cost = wgt + w # 비용 = v로 가는데 드는 가중치 + 현재의 가중치
            if (cost < weight[v]): # 비용이 더 적게 들면
                weight[v] = cost # 더 작은 가중치로 변경
                heapq.heappush(queue, (cost, v)) # 힙에 푸쉬

    return weight[end]

N, E = map(int, input().split())

graph = [[] for _ in range(N+1)]
for _ in range(E):
    a, b, cost = map(int, input().split())
    graph[a].append([b, cost])
    graph[b].append([a, cost])

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

result = min(dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N), dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N))

print(result if result < INF else -1)

---

💭오늘의 회고

오랜만에 풀어본 다익스트라 문제이다.

 

다익스트라를 직접 구현해보아야 하겠지만, 한번 코드를 작성해놓으니 나중에 그대로 긁어와서 응용해서 쓰니 이게 과연 맞는 공부법인지 헷갈린다... ㅋㅋ

 

한번쯤은 안보고 직접 다시 작성해야할 필요가 있다고 생각은 하지만,,, 문제를 빨리 풀고 싶다는 생각에 잘 안되네.

 

어쨋든 문제의 핵심은 다익스트라를 통해 두 점의 최단 경로를 구한 후, 가능한 경우를 선택해 최적의 경로를 찾는것이니

다익스트라를 "구현" 하는것에 초점보단, "어떻게" 활용했는지에 대한 초점이 중요한 것 같다.