[백준 파이썬] 1504 특정한 최단 경로

1504번: 특정한 최단 경로

문제

방향성이 없는 그래프가 주어지고 지나야하는 두 정점이 주어진다. 해당 정점을 모두 지나면서 가장 빠르게 갈 수 있는 길이를 출력하는 문제이다.

---

알고리즘

그래프경로의 최소값을 구해야 하고 가중치가 주어졌으므로 "다익스트라"알고리즘을 사용해야겠다고 생각했다. 

1. 다익스트라 알고리즘

다익스트라 알고리즘을 구현하기 위한 순서는 다음과같다.

1. 자기 자신의 거리(0)를 우선순위 큐에 넣고 다른 노드의 거리를 무한으로 초기화한다.

 

2. 자기 자신을 우선순위 큐에서 뽑아 인접한 정점을 탐색하여 우선순위 큐에 넣는다. 이 때 우선순위 큐안에 노드들은 거리순에 따라 자동으로 정렬된다.

 

3. 우선순위 큐에 가장 앞에 있는 데이터를 뽑아 인접한 정점을 탐색한다. 이 때 이미 우선순위 큐에 있는 노드를 탐색하는 경우 거리가 기존보다 짧을 경우에만 큐에 넣어준다.

 

4. 해당 과정을 큐가 빌때까지 반복한다. 반복된 이후에 거리에 들어있는 값은 최소값이 된다.

 

풀이

문제의 조건에 한번 이동했던 정점을 다시 이동할 수 있다고 했으므로 정점 edges에 다음과 같이 입력받았다.

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

for i in range(E):
    a, b, c = map(int, input().split())
    edges[a].append((b, c))
    edges[b].append((a, c))​

즉 하나의 간선에 대해 양쪽 노드의 정보를 모두 저장하였다.

 

이후 다익스트라를 구현하기 위해 다음과 같이 코드를 작성하였다.

def dijkstra(start, end):
    route = [sys.maxsize] * (N+1)
    route[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, node = heapq.heappop(q)

        if route[node] < dist:
            continue

        for adjacencyNode, adjacencyW in edges[node]:
            cal = route[node] + adjacencyW

            if cal < route[adjacencyNode]:
                route[adjacencyNode] = cal
                heapq.heappush(q, (cal, adjacencyNode))

    return route[end]

 

기본적인 구현방법은 위에서 소개한 다익스트라 알고리즘의 구현방법을 따랐다. 

 

이 때 반드시 지나야 하는 경로가 2가지이므로 가능한 경우의수는 다음과 같다.

출발지점 - v1 -v2 - 도착지점

출발지점 - v2 -v1 - 도착지점

따라서 두가지의 경우의 경로를 모두 계산하였다.

route1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
route2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)

이 때 경로를 찾지 못한 경우에는 경로의 값이 무한대의 값으로 나오므로 

라우트의 값이 무한대일경우 -1일 출력하고 아닐경우 경로의 최소값을 출력하는 코드를 작성하였다.

if route1 >= sys.maxsize and route2 >= sys.maxsize:
    print(-1)

else:
    print(min(route1, route2))

 

---

코드

import sys
import heapq
input = sys.stdin.readline

N, E = map(int, input().split())
edges = [[] for _ in range(N+1)]

for i in range(E):
    a, b, c = map(int, input().split())
    edges[a].append((b, c))
    edges[b].append((a, c))

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


def dijkstra(start, end):
    route = [sys.maxsize] * (N+1)
    route[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, node = heapq.heappop(q)

        if route[node] < dist:
            continue

        for adjacencyNode, adjacencyW in edges[node]:
            cal = route[node] + adjacencyW

            if cal < route[adjacencyNode]:
                route[adjacencyNode] = cal
                heapq.heappush(q, (cal, adjacencyNode))

    return route[end]


route1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
route2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)

if route1 >= sys.maxsize and route2 >= sys.maxsize:
    print(-1)

else:
    print(min(route1, route2))