[백준] 1753번 : 최단경로

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

1753번: 최단경로

가장 간단하게 구현 할 수 있는건 깊이 우선탐색으로 시작 노드로 부터 관련된 노드를 방문하면서 가중치 테이블들 만들어 최대 값보다 작을 경우 업데이트를 하는 방법이다. 아래의 코드는 위의내용을 구현한 코드이다.

import sys 
sys.setrecursionlimit(10**6)

V, E = map(int, input().split()) # 점점의 개수, 간선의 개수
INF = int(10e9)
graph = [[] for _ in range(V+1)]
start = int(input())
for _ in range(E):
    u, v, w = map(int, input().split()) # u에서 v로 가는 가중치 w
    graph[u].append([v,w])

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

def dfs(start, value):
    if dp[start] > value:
        dp[start] = value
        
        while graph[start]:
            v, w = graph[start].pop()
            dfs(v, value + w)
        
dfs(start,0)
for i in range(1,len(dp)):
    if dp[i] == INF:
        print("INF")
    else:
        print(dp[i])

하지만 시간복잡도와 메모리 에러가 발생한다. 문제를 최적화 하기 위해서 데이크스트라 알고리즘을 사용한다.

한 노드에서 다른 노드로 이동할때 가장 짧은거리 순서로 방문한다. 우선순위 큐 인 최소힙큐 를 사용하여 문제를 해결하였다.

import heapq
# import sys 
# sys.setrecursionlimit(10**6)

V, E = map(int, input().split()) # 점점의 개수, 간선의 개수
INF = int(10e9)
graph = [[] for _ in range(V+1)]
start = int(input())
for _ in range(E):
    u, v, w = map(int, input().split()) # u에서 v로 가는 가중치 w
    graph[u].append([v,w])

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

def dfs(start, value):
    if dp[start] > value:
        dp[start] = value
        
        while graph[start]:
            v, w = graph[start].pop()
            dfs(v, value + w)
            
def dijkstra(start):
    queue = []
    dp[start] = 0
    heapq.heappush(queue, [0, start]) # 방문 거리를 최소힙 큐로 구현
    while queue:
        value , now = heapq.heappop(queue) # 가중치, 정점
        for u, v in graph[now]:# 정점, 가중치
            if dp[u] > value+v:
                dp[u] = value+v
                heapq.heappush(queue, [value+v, u])
        
#dfs(start,0)
dijkstra(start)

for i in range(1,len(dp)):
    if dp[i] == INF:
        print("INF")
    else:
        print(dp[i])