백준 / 최단경로 / 1753번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 최단경로 / 1753번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/1753

 

문제 설명

 

---

나의 풀이

 

from collections import deque

INF = 1e9

V, E = map(int, input().split())
S = int(input())

graph = {i : [] for i in range(1, V + 1)}

for _ in range(E):
    v, e, dist = map(int, input().split())
    graph[v].append((e, dist))

def dijsktra(graph, Start):
    q = deque([(Start, 0)])
    visited = [INF] * (len(graph) + 1)
    visited[Start] = 0

    while q:
        current, dis = q.popleft()

        if visited[current] < dis:
            continue

        for next, weight in graph[current]:
            nextdis = dis + weight
            if visited[next] > nextdis:
                visited[next] = nextdis
                q.append((next, nextdis))

    return visited 

result = dijsktra(graph, S)
del result[0]

for i in result:
    if i == INF:
        print("INF")
    else:
        print(i)

다익스트라는 deque를 이용해서 풀면 시간 초과가 발생한다.

import heapq
import sys

input = sys.stdin.read
INF = float('inf')

def dijkstra(V, E, K, edges):
    graph = [[] for _ in range(V + 1)]
    
    for u, v, w in edges:
        graph[u].append((v, w))
    
    distances = [INF] * (V + 1)
    distances[K] = 0
    pq = [(0, K)]  # (distance, node)

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for adjacent, weight in graph[current_node]:
            distance = current_distance + weight

            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(pq, (distance, adjacent))

    return distances

# Read input
data = input().split()
idx = 0

V = int(data[idx])
idx += 1
E = int(data[idx])
idx += 1
K = int(data[idx])
idx += 1

edges = []
for _ in range(E):
    u = int(data[idx])
    idx += 1
    v = int(data[idx])
    idx += 1
    w = int(data[idx])
    idx += 1
    edges.append((u, v, w))

# Run dijkstra and get the result
distances = dijkstra(V, E, K, edges)

# Print the results
for i in range(1, V + 1):
    if distances[i] == INF:
        print("INF")
    else:
        print(distances[i])

힙을 사용하여 문제를 풀면 최선의 경로를 먼저 뽑기 때문에 최적의 해를 구할 수 있다.

---

※ 알아야 할 것

 

https://newkimjiwon.tistory.com/85

다익스트라 알고리즘(Dijkstra)