[탐색/다익스트라] 백준 1504 특정한 최단 경로 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1504번: 특정한 최단 경로

 

 

2. 문제 풀이

 1번 정점에서 N번 정점으로 가는 최단 거리를 구하는 문제입니다. 단, 정점 v1, v2를 꼭 지나야 합니다.

 

2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

[Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

 '다익스트라' 알고리즘을 이용해서 최단 경로를 구하는 문제입니다. 다익스트라에 대한 설명과 코드는 위 링크에서 보실 수 있습니다.

 

Path1) 1번 => V1 => V2 => N번
Path2) 1번 => V2 => V1 => N번

 두 정점을 지나 N번으로 가는 경로는 위 2가지입니다. Path1, 2를 구하기 위해서, 총 3번의 다익스트라 알고리즘을 사용합니다.

 시작점을 1번, V1, V2로 해서 각 노드까지의 최단 거리를 구합니다. 그 이후에 각 구간별 최단 거리를 합해서 총 최단거리를 계산합니다.

 

Path1) 1번에서 V1 + V1에서 V2 + V2에서 N번
Path2) 1번에서 V2 + V2에서 V1 + V1에서 N번

 

 

 

3. 코드

import heapq  # 우선순위 큐 구현을 위함
import sys
input = sys.stdin.readline

# 입력
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))
v1, v2 = map(int, input().split())  # 반드시 지나야할 정점


# 다익스트라 최적경로 탐색
def dijkstra(graph, start):
    distances = [int(1e9)] * (N+1)  # 처음 초기값은 무한대
    distances[start] = 0  # 시작 노드까지의 거리는 0
    queue = []
    heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작

    while queue:  # queue에 남아있는 노드가 없을 때까지 탐색
        dist, node = heapq.heappop(queue)  # 탐색할 노드, 거리

        # 기존 최단거리보다 멀다면 무시
        if distances[node] < dist:
            continue

        # 노드와 연결된 인접노드 탐색
        for next_node, next_dist in graph[node]:
            distance = dist + next_dist  # 인접노드까지의 거리
            if distance < distances[next_node]:  # 기존 거리 보다 짧으면 갱신
                distances[next_node] = distance
                heapq.heappush(queue, [distance, next_node])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입
    return distances

 그래프를 입력받고, 다익스트라 알고리즘을 구현합니다. 방향이 없는 그래프이므로, 간선으로 연결된 노드는 양쪽에서 오갈 수 있습니다.

 

 

dist_start = dijkstra(graph, 1)
dist_v1 = dijkstra(graph, v1)
dist_v2 = dijkstra(graph, v2)

path1 = dist_start[v1]+dist_v1[v2]+dist_v2[N]
path2 = dist_start[v2]+dist_v2[v1]+dist_v1[N]

if path1 >= int(1e9) and path2 >= int(1e9):
    print(-1)
else:
    print(min(path1, path2))

 총 3번의 다익스트라를 사용해서 1, V1, V2 노드에서 각 노드까지의 최단거리를 계산합니다.

 이후 path1, path2를 계산하고 비교해서 최단거리를 출력합니다.