[백준 1504 파이썬] 특정한 최단 경로 (골드4, 다익스트라)

알고리즘 유형 : 다익스트라
풀이 참고 없이 스스로 풀었나요? : △

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

소스 코드(파이썬)

import sys
import heapq
input = sys.stdin.readline


# 입출력 ---------------------------------------------------
N, E = map(int, input().split())
edges = [[] for i 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:
        cnt_w, cnt_node = heapq.heappop(q)
        
        if route[cnt_node] < cnt_w:
            continue
        
        for adjacency_node, adjacency_w in edges[cnt_node]:
            cal_w = route[cnt_node] + adjacency_w
            
            if cal_w < route[adjacency_node]:
                route[adjacency_node] = cal_w
                heapq.heappush(q, (cal_w, adjacency_node))
    
    return route[end]

# 최단 경로는 두 가지 가능한 경우의 수가 있다. (1 > v1 > v2 > N or 2 > v2 > v1 > N)
route1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
route2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)

# 만약 위 식에서 하나의 최단 거리라도 존재하지 않으면 그 경로의 값은 sys.maxsize가 된다.
# 이 경우를 조건문으로 걸러주어 상황에 맞는 올바른 답을 출력해준다.
if route1 >= sys.maxsize and route2 >= sys.maxsize:
    print(-1)
else:
    print(min(route1, route2))

풀이 요약

1. 이 문제는 무방향 가중치 그래프에서 특정 노드에서 특정 노드까지의 최단 거리를 구하는 것이 핵심이다.

   그 것은 다익스트라 알고리즘으로 특정 노드에서 모든 노드까지의 최단 거리를 구하고, 구하고자 하는 도착 노드까지의 최단 거리만을 리턴하도록 함수를 작성하면 된다.

2. 유의해야할 점은 무방향 그래프이므로, 간선 정보를 변수에 저장할 때, 하나의 간선 정보에 대해 양쪽 노드 모두 한 번씩 정보를 저장해줘야한다.

3. 두 정점을 거쳐서 목적 노드로 가는 경우의 수는 두 가지가 있다.

   1번 노드 > v1 > v2 > N번 노드
1번 노드 > v2 > v1 > N번 노드

   부분 경로 최단 거리를 다익스트라로 구해서 더해주면 경로 가중치 최단 거리를 구할 수 있다.

   이 때, 위 경우의 수에 따라 경로 최단 거리값을 구할 때, 부분 경로 중 하나라도 최단 거리가 존재하지 않으면, 그 전체 경로의 최단 거리 값이 sys.maxsize 이상의 값이 된다. 즉, 구한 경로의 값이 sys.maxsize 이상이면 그 경로는 최단 거리가 존재하지 않는 경우인 것이다. 이를 조건문으로 잘 걸러서 답을 출력해주면 된다.

배운 점, 어려웠던 점

• 다익스트라 알고리즘을 응용하는 경험이 되었고, 활용에 더 익숙해질 수 있어 유익했다.

• 무방향 그래프라는 점을 놓쳐서 간선 정보 저장할 때 한쪽 방향만 저장하는 실수를 했고, 다익스트라 알고리즘에서도 현재 탐색 노드에 대한 인접 노드의 최단 거리를 갱신해주고 힙에 넣을 때, 새로 갱신된 최단 거리를 안 넣고 갱신 전 값을 넣어버리는 실수를 해서 다른 사람 풀이를 보고 찾아냈다. 다익스트라의 활용이 아직 덜 익숙한가보다.