[백준] 1753번 : 최단경로

문제

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

풀이

[백준] 1753 : 최단경로 🥇(골드 4)
🎯 25.066%
⏰ 걸린 시간 : 43분
⏲ 시간복잡도
: 다익스트라 -> O(ElogV) : EV인데 우선순위 큐 사용해주면 탐색이 logV로 줄어든다.

• 알고리즘 유형 : [다익스트라]

✅ 문제 요약

0. 첫째 줄에 정점의 개수 V와 간선의 개수 E가 둘째 줄에는 시작 정점의 번호가 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수가 (u, v, w)가 순서대로 주어진다.
1. 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하여라.

✅ 출력

• 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

✅ 풀이방법 & 다익스트라 알고리즘로 푼 이유?

✔️ 전형적인 최단 경로 문제이다.
0. 다익스트라 : 한 정점에서 모든 정점까지의 거리를 계산함
1. 가는 길을 택하는데 최소의 거리 길이를 택하여서 가야하기 때문이다.
2. 플로이드 워셜의 경우는 시간 복잡도가 O(V^3)인데 D의 입력이 10,000이기 때문에 2초를 초과 할 수 있다.

코드(code)

import sys
import heapq
input = sys.stdin.readline
V, E = map(int, input().split())
K = int(input())
INF = int(1e9)
graph = [[] for _ in range(V+1)]
path = [INF] * (V+1)

for i in range(E):
    u, v, w = map(int,input().split())
    graph[u].append((v,w))

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    path[start] = 0
    while q:

        length, now = heapq.heappop(q)

        if path[now] < length: 
            continue

        for e,l in graph[now]:
            now_length = length + l
            if now_length < path[e]:
                path[e] = now_length
                heapq.heappush(q,(now_length,e))


dijkstra(K)

# i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력
for i in range(1,V+1):
    if path[i] == INF:
        print('INF')
    else:
        print(path[i])

회고

😼 다익스트라 알고리즘 연습 또 연습!!

• 가중치가 있는 최단거리를 찾는 알고리즘으로는 다익스트라가 적합하다.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/BFS_DFS/Dijkstra/1916(%EC%B5%9C%EC%86%8C%EB%B9%84%EC%9A%A9%20%EA%B5%AC%ED%95%98%EA%B8%B0).py