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

 

 

문제 링크

 

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

 

문제 풀이

 

단순한 다익스트라 문제인 줄 알았는데 예상치 못한 예외가 자꾸 튀어나와

낮은 정답률이 이해되는 문제였습니다.

 

실패 풀이)

처음에 실패했던 풀이는 최소비용 구하기2 문제처럼 route 배열을 따로 두고

이동경로를 매번 저장하는 방식이었습니다.

route를 갱신하며 할당하기 때문에 문제가 없을 줄 알았으나

메모리 초과로 인해 실패했습니다.

 

 

다익스트라의 기본 구조를 활용하면서 문제를 풀이하는 방법을 고민했습니다.

문제에서는 두 정점이 주어지고 1번에서 N번까지 이동하는 동안 두 정점을 무조건 거쳐야합니다.

그렇다면 1번에서 N번으로 이동하는 동안 경로의 경우의 수는 총 두 가지가 나옵니다.

1. (1번~정점1) - (정점1~정점2) - (정점2~N번)

2. (1번~정점2) - (정점2~정점1) - (정점1~N번)

 

두 경우의 수 안에 있는 3개의 경로에 대한 최소 거리를 각각 구하여 더해주면

두 경우의 수 중 최솟값이 결괏값이 됩니다.

 

path1 = dijkstra(1, route1) + dijkstra(route1, route2) + dijkstra(route2, n)
path2 = dijkstra(1, route2) + dijkstra(route2, route1) + dijkstra(route1, n)

 

모든 경우의 수를 파악한 줄 알았으나, 문제를 제대로 읽지 않아 한 가지 간과했던 사실이 있습니다.

정점1과 정점2가 1번이나 N번이 될 수도 있습니다.

따라서, 정점1이 1번이 되고 정점2가 N번이 되는 경우도 하나의 path로 추가해줘야 합니다.

 

path3 = 1e9
if (route1 == 1 and route2 == n) or (route1 == n and route2 == 1):
    path3 = dijkstra(1, n)

 

이렇게 도출한 3가지 경로 중 최소거리 값을 출력하면 됩니다.

 

 

전체 코드

import heapq, sys
input = sys.stdin.readline

def dijkstra(start, end):
    distance = [1e9] * (n + 1)
    distance[start] = 0
    q = [(0, start)]
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for node, weight in graph[now]:
            weight += dist
            if weight < distance[node]:
                distance[node] = weight
                heapq.heappush(q, (weight, node))
    return distance[end]


n, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(e):
    a, b, weight = map(int, input().split())
    graph[a].append((b, weight))
    graph[b].append((a, weight))
route1, route2 = map(int, input().split())
path1 = dijkstra(1, route1) + dijkstra(route1, route2) + dijkstra(route2, n)
path2 = dijkstra(1, route2) + dijkstra(route2, route1) + dijkstra(route1, n)
path3 = 1e9
if (route1 == 1 and route2 == n) or (route1 == n and route2 == 1):
    path3 = dijkstra(1, n)

result = min(path1, path2, path3)
print(result if result < 1e9 else -1)