[다익스트라] 백준 1753: 최단경로

문제: 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

---

입력: 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

---

 

이 문제는 다익스트라를 사용하는 문제 중 가장 기본적인 문제라고 생각한다. 근데 어려웠다. 다익스트라라는 알고리즘이 갖는 기본적인 난이도가 높아서 그런 것일 수도 있고, 내가 다익스트라를 활용하는 문제를 많이 안 풀어봐서 그런 걸수도 있다. 그렇기 때문에 코드를 보기 전에 다익스트라에 대해 간단히 정리하고 넘어가겠다.

 

다익스트라

사용처: 가중치가 있는 경로의 최단거리를 구할 때 사용.

 

로직

1. 시작점 S가 있다. 그 S와 선 1개로 연결되어 있는 노드를 탐색하고, 해당 노드까지의 거리를 기록한다.

2. 1번에서 탐색한 노드들 중 S와 가장 거리가 가까운 노드를 선택한다.

3. 선택한 노드에서 다른 노드까지의 거리를 계산한다. (연결되어있는 노드에 대해서만)

4. 만약 1번에서 기록된 S to A 노드의 길이가 3번에서 계산된 S to B to A의 길이보다 길다면? 값을 갱신해준다.

5. 위의 로직을 반복하여 실행한다. 언제까지? 모든 노드를 가까운 순으로 방문할 때 까지.

 

 

답을 내는 것은 그리 어렵지 않으나, 메모리 초과나 시간초과를 해결하는데 많은 시간이 걸렸다. 결과적으론 인접행렬을 인접리스트로 수정하여 코드를 바꿨더니 통과가 되었다.

 

아래는 풀이 코드이다.

import sys
from pprint import pprint
from collections import deque

def di(K):
    queue = deque()
    visited[K] = 1
    ans_list[K] = 0
    for i in range(len(relation_arr[K])):
        ans_list[relation_arr[K][i][0]] = relation_arr[K][i][1]

    # pprint(ans_list)
    min_node = K
    min_node_length = 1000000000
    for i in range(1, len(ans_list)):
        if ans_list[i] < min_node_length:
            min_node_length = ans_list[i]
            min_node = i
    queue.append(min_node)
    # print(min_node)
    while queue: # 노드를 모두 방문하기 전 까지
        # K노드에서 가까이 있는 노드 위주로 진행. min_node에서 시작하는 순회
        # print(visited)
        min_node = queue.popleft()
        before_node = ans_list[min_node] # K 에서 min_node까지 이동하는 값
        visited[min_node] = 1

        for i in range(len(relation_arr[min_node])):
            if relation_arr[min_node][i][1] + before_node < ans_list[relation_arr[min_node][i][0]]:
                ans_list[relation_arr[min_node][i][0]] = relation_arr[min_node][i][1] + before_node

        min_node_length = 1000000000
        # print(ans_list)
        for i in range(1, len(ans_list)):
            if visited[i] == 0 and ans_list[i] < min_node_length:
                min_node_length = ans_list[i]
                min_node = i
        if min_node_length == 1000000000:
            pass
        else:
            queue.append(min_node)
        # print(min_node, min_node_length)


V, E = map(int, input().split()) # V: 정점의 개수, E: 간선의 개수
K = int(input()) # 시작점
arr = []
for i in range(E):
    arr.append(list(map(int, input().split()))) # u, v, w -> u에서 v로 가는 간선의 가중치는 w

# 방향그래프가 주어지면 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성
# 가중치를 이차원 리스트에 표현해보면 좋을 것 같다.
relation_arr = [[] for _ in range(V+1)] # 정점의 번호와 인덱스를 일치시켜주는 작업
# 인접 리스트를 이용해 메모리 단축
for i in range(len(arr)):
    relation_arr[arr[i][0]].append((arr[i][1], arr[i][2])) # relation_arr의 인덱스값이 출발점, 튜플의 첫 값이 도착점, 두번째 값이 가중치

# pprint(relation_arr)

ans_list = [10**9] * (V+1) # K에서 각 노드까지 걸리는 최단 거리를 저장할 예정
visited = [0] * (V+1)
di(K)
# 출력: i번째 줄에 시작점에서 i번째 간선으로의 최단거리를 출력. 자기 자신은 0, 경로 존재하지 않으면 INF 출력
for i in range(1, len(ans_list)):
    if ans_list[i] == 10**9:
        print('INF')
    else:
        print(ans_list[i])