1753번 - 최단경로

출처: 백준 알고리즘

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

1753번: 최단경로

 

1753번 - 최단경로

 

문제 요약:

    (1) 방향 그래프와 시작 정점이 주어진다.

    (2) 시작 정점에서 모든 정점에 대한 최단경로를 계산하고 출력한다.

 

문제 해결(파이썬):

    A. 입력

    B. 다익스트라 알고리즘 구현

    C. 출력

    - 시작 지점 = 0

    - 시작 정점에서 갈 수 있는 정점 = 최소 거리

    - 시작 정점에서 갈 수 없는 정점 = INF

 

미리 공부할 내용:

    1. 다익스트라 알고리즘

    2. 우선순위 큐(queue)

    3. 힙(heap)

 

알고리즘:

    A. 입력

     1. 정점의 개수(V), 간선의 개수(E), 시작 정점(K)

        - (범위: 0 < V < 20,001, 0 < E < 300,001, 0 < K < V + 1)

     2. 출발 정점(u), 도착 정점(v), 가중치(w)

        - (범위 및 조건: 0 < u, v < V + 1, -1 < w < 11, u != v)

     3. sys.stdin.readline()이 input()보다 입력 속도가 빠르므로 사용하는 것이 좋다.

     4. 그래프는 인접 리스트로 저장하는 것이 딕셔너리로 저장하는 것보다 빠르다.

 

예제 그림

         - 위의 그림을 '인접 리스트'와 '딕셔너리' 두 가지 방법으로 저장할 수 있다.

데이터 저장

         - '인접 리스트'로 저장해야 빠르게 값들을 찾아서 가져올 수 있다.

 

    B. 다익스트라 알고리즘 구현

     1. 정점의 개수만큼 리스트(distances) 생성 (시작 정점에서 다른 정점들간의 최소 거리를 저장하는 리스트)

     2. distances를 10⁸으로 초기화

     3. distances에서 시작 정점은 0으로 저장

     4. 우선순위큐(queue)에 시작 정점을 저장

     5. 우선순위큐가 빌 때까지 반복

         5-1. 우선순위가 제일 작은 정점(cur_node)과 거리(cur_dis) 추출

         5-2. 기존 최소 거리보다 방금 추출한 거리가 길면 갱신을 하지 않고 다음 정점으로 이동

         5-3. cur_node와 연결된 정점들 탐색

             5-3-1. 연결된 정점 중에서 해당 정점을 거쳐서 지나가는 거리가 짧은 경우

             5-3-2. 최소 거리를 갱신

             5-3-3. 해당 정점의 인접된 정점들을 찾기 위해, 우선순위큐에 삽입

 

    C. 출력

     - 소스코드 참고

 

 

소스코드(전체적인 코드):

import heapq
import sys
 
# 상수
inf = 10 ** 8
 
def dijkstra(graph, start, V):
 
    # start로부터의 거리 값을 저장
    distances = [inf] * (V + 1)
    distances[start] = 0 # 시작(start) 값은 0으로 설정
    queue = []
    heapq.heappush(queue, [distances[start], start]) # 시작노드부터 탐색 시작
 
    # queue에 남아있는 노드가 없을 때까지 반복
    while queue:
        # 탐색할 노드, 거리를 가져옴
        cur_dis, cur_node = heapq.heappop(queue)
 
        # 기존에 있는 거리보다 길면, 갱신 x
        if distances[cur_node] < cur_dis:
            continue
 
        for new_node, new_dis in graph[cur_node]:
            dis = cur_dis + new_dis # 해당 노드를 거쳐서 지나 가는 경우의 길이
            if dis < distances[new_node]: # 기존 거리보다 작은 경우, 갱신
                distances[new_node] = dis
                heapq.heappush(queue, [dis, new_node]) # 다음 인접 거리를 계산을 위해 큐에 삽입
 
    return distances
 
# 입력
V, E = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())
graph = [[] for _ in range(V + 1)]
for i in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append([v, w])
 
 
# 출력
for i in dijkstra(graph, K, V)[1:]:
    print(i if i != inf else "INF")

 

한줄평:

     - 자료구조를 이해하고 구현하면서 여러 문제에 적용해볼 수 있도록 노력하자.