✏️ 1753

문제

👀 풀이

이와 같은 다익스트라 문제는 두 가지 방법으로 풀 수 있다.
1. 순차탐색
2. 힙
을 이용한 방법 두 가지이다.

두 가지 방법으로 풀기 전에 두 코드에서 필요한 것은 graph 와 distance 테이블 이다.

• graph : 이 문제의 (u,v,w) 를 정리한 테이블
• distance : start 부터 각 노드까지의 최단 거리를 표현한 테이블

< 1. 순차탐색을 활용한 방법 >

# 1753

# <by 순차탐색>

import sys

INF = int(1e9)

V , E = map(int, sys.stdin.readline().split()) # 정점 / 간선 

start = int(sys.stdin.readline())

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

distance = [INF for _ in range(V+1)]

visited = [False for _ in range(V+1)]

for _ in range(E) :
    u,v,w = map(int, sys.stdin.readline().split())
    graph[u].append((v,w))

# 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 번호 반환
def get_smaller_node() :
    min_value = INF
    index = 0
    for i in range(1,V+1) :
        if not visited[i] and min_value > distance[i] :
            min_value = distance[i]
            index = i
    return index

# 다익스트라
def dijkstra() :
    distance[start] = 0
    visited[start] = True

    # 일단 출발노드의 인접노드에 대해서 최단거리 테이블에 넣기
    for a,b in graph[start] : # (2,2) , (3,3)
        distance[a] = b

    for _ in range(V-1) : # 이때 (V-1) 인 이유? : start 제외하고 모든 노드 검사하기 위해
        now = get_smaller_node()
        visited[now] = True
        for a,b in graph[now] : # (3,4),(4,5)
            cost = distance[now] + b
            if cost < distance[a] :
                distance[a] = cost

dijkstra()

for i in range(1,V+1) :
    if distance[i] == INF :
        print("INF")
    else :
        print(distance[i])

이때 순차탐색은 O(N^2)의 시간복잡도를 가지기 때문에 이 풀이로 하면 시간초과가 뜬다 🤣

< 2. 힙을 활용한 방법 >

힙의 경우 파이썬에서 제공해주는 heapq 라이브러리를 사용한다 !!

# 1753

# <by 힙>

import heapq
import sys

INF = int(1e9)

V, E = map(int, sys.stdin.readline().split())

start = int(sys.stdin.readline())

graph = [[] for _ in range(V+1)]
distance = [INF for _ in range(V+1)]

for _ in range(E) :
    u,v,w = map(int, sys.stdin.readline().split())
    graph[u].append((v,w))

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

    while q :
        dist, now = heapq.heappop(q)
        
        # 순차탐색과 다르게 visited 테이블 대신 조건문으로 방문 여부 처리 !
        if distance[now] < dist :
            continue

        for a,b in graph[now] : # (2,2) (3,3)
            cost = distance[now] + b
            if cost < distance[a] :
                distance[a] = cost
                heapq.heappush(q,(cost, a))

dijkstra()

for i in range(1, V+1) :
    if distance[i] == INF :
        print("INF")
    else :
        print(distance[i])