[Python] 1753 - 최단경로 (골드4)

1. 문제 설명

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

1753번: 최단경로

다익스트라 알고리즘은 아직도 명확하게 머리에 잡히지 않은 알고리즘 중 하나다.

사용엔 지장이 없는데 누가 설명해달라고 하면 자신이 없는 단계

블로그 포스팅 끝나면 문제 몇 개 더 풀어봐야겠다.

 

---

2. 아이디어

문제를 읽자마자 다익스트라 알고리즘을 쓰면 되겠다 싶어서 썼는데 시간 초과가 났다.

인접 행렬로 최단 거리 노드를 갱신하려니 리스트가 너무 방대해서 읽어들이는데 어지간히 오래 걸렸나보다.

인접 리스트를 사용해서 속도를 높여야 한다.

 

좀더 자세히 파고 들자면..

전자는 시간복잡도가 약 \(O(V^{2})\)이므로 4억 개의 데이터를 1초 내에 처리하지 못 한다.

하지만 힙큐를 쓰면 \(O((V+E)logV)\) 이므로 시간을 훨씬 단축시킬 수 있다.

 

우선 거리를 모두 INF로 초기화시켜두고 힙에는 (비용, 출발노드)를 넣는다.

root가 1이라고 치면 1과 연결되어있는 그래프 정보를 읽어서 현재까지 이동한 거리 + 가중치만큼

거리에 누적시켜서 distance 리스트의 다음 노드 인덱스 위치에 저장한다.

 

중간에 비교를 통해서 이미 저장된 거리 비용이 더 최소인 값이 들어있다면

건너뛰어서 시간을 단축시킬 수 있다.

(좌)인접행렬, (우)인접리스트

 

---

3. 코드

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)

n, e = map(int, input().split()) # 정점, 간선 개수

def dijkstra(start, distance, graph):
    global n

    heap = []
    heapq.heappush(heap, (0, start))
    distance[start] = 0
    
    while heap:
        dist, now = heapq.heappop(heap)
        if distance[now] < dist: # 예외 처리, 추가하려는 노드보다 짧은 노선이 이미 저장되어 있다면 패스
            continue
        for i in graph[now]: # 인접 노드 호출
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(heap, (cost, i[0]))

def solution():
    global n, e
    
    k = int(input()) # 시작 정점 위치
    distance = [INF] * (n+1)  # 최단 거리
    graph = [[] for _ in range(n+1)] # 간선 정보
    for _ in range(e):
        u, v, w = map(int, input().split())
        graph[u].append((v, w)) # u -> v 정점으로 이동하는 비용 w

    dijkstra(k, distance, graph)

    for i in range(1, n+1): # 모든 노드로 가기 위한 최단 거리 출력
        if distance[i] == INF: # 도달할 수 없는 경우
            print("INF")
        else:
            print(distance[i])

solution()

 

시간초과 나는 풀이

import sys

input = sys.stdin.readline
INF = int(1e9)

n, e = map(int, input().split()) # 정점, 간선 개수

def get_smallest_node(distance, visited): # 방문하지 않는 노드 중에서 최단거리가 가장 짧은 노드 반환
    global n

    min_value = INF
    idx = 0
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            idx = i
    return idx

def dijkstra(start, distance, visited, graph):
    global n

    distance[start] = 0 # 시작 노드
    visited[start] = True
    for j in graph[start]: # 출발 노드와 인접 노드에 대한 최단거리 테이블 갱신
        distance[j[0]] = j[1]

    for i in range(n-1): # 모든 노드에 대해 반복
        now = get_smallest_node(distance, visited) # 현재 최단 거리가 가장 짧은 노드를 꺼내어 방문처리
        visited[now] = True
        for j in graph[now]: # 선택된 노드와 연결된 다른 노드 확인
            cost = distance[now] + j[1] # 선택된 노드를 통해 가는 비용 다시 계산
            if cost < distance[j[0]]:
                distance[j[0]] = cost # 최단거리 테이블 갱신

def solution():
    global n, e
    
    k = int(input()) # 시작 정점 위치
    visited = [False] * (n+1) # 방문 체크
    distance = [INF] * (n+1)  # 최단 거리
    graph = [[] for _ in range(n+1)] # 간선 정보
    for _ in range(e):
        u, v, w = map(int, input().split())
        graph[u].append((v, w)) # u -> v 정점으로 이동하는 비용 w

    dijkstra(k, distance, visited, graph)

    for i in range(1, n+1): # 모든 노드로 가기 위한 최단 거리 출력
        if distance[i] == INF: # 도달할 수 없는 경우
            print("INF")
        else:
            print(distance[i])

solution()