[백준-파이썬] 1753: 최단 경로

문제 보러 가기!

아이디어

라고 할 것도 없는 것 같다. 다익스트라로 풀었다..
다익스트라..는 전에도 들어는 봤지만, 딱히 공부하지는 않았었다.
이번 기회에 다익스트라를 공부할 수 있었다!

참고한 자료

안경잡이 개발자님의 글과 레드캐럿님의 벨로그 포스팅!!. 안경잡이 개발자님은 영상으로도 있어서, 다익스트라가 뭔지 이해하는 데 도움이 되었고, 레드캐럿님의 벨로그 포스팅은 파이썬 코드라서 코드 구현을 어떻게 해야 할지 알 수 있었다!! 또 플로이드워셜과의 차이점도 궁금했는데, 잘 설명해주셔서 좋았다 ㅎㅎ

코드 👩‍💻

import heapq
import sys

input = sys.stdin.readline

V, E = map(int, input().split())  # 노드 개수, 간선 개수
start = int(input())  # 시작점
INF = 10*20000+1  # u-> v로 가는 가중치는 최대 10까지 들어온다고 하고, 정점의 개수는 2만개까지 들어온다.. 그래서 수를 이렇게 정했다.

arr = [[] for _ in range(V + 1)]  # 연결된 노드 있으면, 그 노드와 가는 데 드는 비용을 저장한 리스트

for _ in range(E):  # 간선 정보 입력받기
    u, v, w = map(int, input().split())
    arr[u].append([w, v])  # u에서 v로 갈 때 비용 w

distance = [INF] * (V + 1)  # start에서 각각 노드로 갈 때 최단 비용을 저장한 리스트
# 다익스트라
Q = []
heapq.heappush(Q, (0, start))  # start에서 start로 가는 비용(0). 인덱스를 큐에 넣고 시작
distance[start] = 0

while Q:
    now_cost, now_idx = heapq.heappop(Q)  # 가장 최단 거리인 노드 정보 꺼냄 (인덱스, 비용)
    if distance[now_idx] < now_cost:  # 최단 거리가 아니라면 그만 두기
        continue

    for info in arr[now_idx]:  # 현재 노드와 연결된 다른 노드
        now_next_cost, next_idx = info  # 연결된 다른 노드 인덱스, 현재 노드-> 그 노드 가는 데 드는 비용
        next_idx_cost = now_cost + now_next_cost  # 출발점 -> 현재 노드 -> next_idx로 이동하는 데 드는 비용
        if next_idx_cost < distance[next_idx]:  # 거쳐서 가는 것이, 안 거쳐 가는 것보다 비용이 적게 들면
            distance[next_idx] = next_idx_cost  # 출발점 -> next_idx 가는 비용을 업데이트
            heapq.heappush(Q, (next_idx_cost, next_idx))

# 출력
for i in range(1, V+1):
    ans = distance[i]
    if ans == INF:
        ans = 'INF'
    print(ans)

배운 것

다익스트라 배운 것 정리는 다음 기회에 해보려고 한다.
또 우선순위큐!!도 배웠다.
다익스트라 구현에는 대표적으로 두 가지 버전이 있다.
순차적으로 탐색하는 버전과 우선순위 큐를 활용한 버전..! 우선순위 큐를 이용한 게 시간 복잡도가 작다.
그래서 우선순위 큐 버전으로 코드를 짰는데, 처음에는 시간 초과가 나왔다. 우선순위 큐를 활용했는데도 시간 초과가 나오다니..ㅠㅠ 라는 생각을 하면서, 더 찾아봤다.
그랬더니 우선순위 큐에 넣는 순서!!가 중요하다는 걸 알게 되었다!
처음에는 (위치, 가중치) 순서로 푸시를 했다. 우선순위 큐는 첫 번째 값을 비교한 다음에, 같으면 다음 값을 비교한다고 한다. 위치 인덱스가 같은 것은 여러 개 있는데, 가중치가 작은 걸 먼저 넣어줘야지 일하는 게 줄어들 것이다.(그때까지의 최단거리보다 크면, continue하니까) 그러니까 (가중치, 위치) 순서로 넣어야 하는 것이었다!!