[Python/백준] 1753. 최단거리

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

다익스트라 알고리즘

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

---

풀이

리스트를 사용한 다익스트라

→ 시간초과(O(V^2))

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

s = int(input())

for _ in range(m):
    x, y, w = map(int, input().split())
    graph[x].append((y, w))

def dijkstra(node):
    # 3. 시작 정점까지의 최단 거리는 0으로
    distance[node] = 0

    # 7. 4. ~ 6. 단계를 n번 반복
    # for _ in range(n):
    for _ in range(n - 1):
        
        # 4. 아직 방문하지 않은 놈들 중에서, distance(최단 거리) 가장 작은 놈 찾기
        node, min_dist = -1, INF
        for i in range(1, n + 1):
            if not visited[i] and distance[i] < min_dist:
                node = i
                min_dist = distance[i]
                
        # 5. 최단 거리를 확정
        visited[node] = True

        # 6. 해당 정점과 인접한 정점에 대해 최단 거리를 갱신
        for next_node, dist in graph[node]:
            next_dist = min_dist + dist

            if next_dist < distance[next_node]:
                distance[next_node] = next_dist

INF = float('inf')

# 1. distance 리스트 정의
distance = [INF] * (n + 1)

# 2. visited 리스트 정의
visited = [False] * (n + 1)

dijkstra(s)

for d in distance[1:]:
    if d == INF:
        print("INF")
    else:
        print(d)

 

최소 힙을 사용한 다익스트라

→ O(ElogV)

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
s = int(input())

graph = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y, w = map(int, input().split())
    graph[x].append((y, w))

INF = float('inf')
distance = [INF] * (n + 1)

def dijkstra(node):
    # 1. 시작 정점 초기화
    distance[node] = 0
    heap = [(0, node)]

    # 2. 힙이 빌 때까지
    while heap:
        # 3. 힙에서 하나 뽑아서
        min_dist, node = heappop(heap)

        # 4. 쓰레기 값이면 튕기기
        if min_dist > distance[node]:
            continue

        # 5. 그 정점에 인접한 정점들에 대해,
        for next_node, dist in graph[node]:
            # 새롭게 갱신할 지 말지 관찰할 next_node의 거리는,
            # 내가 보는 기준인 node까지의 최단 거리 + 거기서 next_node까지의 거리
            next_dist = min_dist + dist
            # 6. 거기에서 가는 거리가 더 짧으면 distance 갱신
            if next_dist < distance[next_node]:
                distance[next_node] = next_dist
                heappush(heap, (next_dist, next_node))

dijkstra(s)

for d in distance[1:]:
    if d == INF:
        print('INF')
    else:
        print(d)

---

250228 재풀이

다익스트라 6단계 기억하기

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

# v, e 첫째줄에 주어지고
# 정점은 1부터 시작
# 둘째 줄은 시작 정점 번호 k
# 셋째 줄부터 간선 정보 e개
# 방향 그래프
# 여러 개의 간선 존재 가능함에 유의
# k에서 출발해 각 정점까지의 최단 거리 값 출력. k점은 0으로 출력
# 경로가 존재하지 않으면 INF 출력

def dijkstra(node):
    # 1. 시작 정점 초기화
    distance[node] = 0
    heap = [(0, node)]
    # 2. 힙이 빌 때까지
    while heap:
        # 3. 힙에서 하나 뽑아서
        min_dist, node = heappop(heap)

        # 4. 쓰레기 값이면 튕기기
        if min_dist > distance[node]:
            continue

        # 5. 그 정점에 인접한 정점들에 대해,
        for next_node, dist in graph[node]:
            next_dist = min_dist + dist
            # 6. 거기에서 가는 거리가 더 짧으면 distance 갱신
            if next_dist < distance[next_node]:
                distance[next_node] = next_dist
                heappush(heap, (next_dist, next_node))

v, e = map(int, input().split())
k = int(input())
graph = [[] for _ in range(v + 1)]
for _ in range(e):
    x, y, w = map(int, input().split())
    graph[x].append((y, w))

INF = float('inf')
distance = [INF] * (v + 1)
dijkstra(k)
for dist in distance[1:]:
    if dist == INF:
        print('INF')
    else:
        print(dist)