[BOJ] 1753 : 최단경로 [그래프탐색](Python)

문제 링크

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

1753번: 최단경로

소스 코드

import sys
import heapq

def main():
    V,E = map(int,sys.stdin.readline().strip().split()) # 정점, 간선
    K = int(sys.stdin.readline().strip()) # 시작점

    INF = int(1e9) # 초기값
    graph = [[] for _ in range(V+1)]
    distance = [INF] * (V+1)

    for _ in range(E):
        u,v,w = map(int,sys.stdin.readline().strip().split())
        graph[u].append((v,w)) # (정점, 가중치)

    def dijkstra(start): # 최단경로 탐색
        queue = []
        heapq.heappush(queue,(0,start)) # (가중치, 정점)
        distance[start] = 0

        while queue:
            dist,now = heapq.heappop(queue)
            if distance[now] < dist: # 최단 경로가 아니라면
                continue

            for v,w in graph[now]:
                cost = dist + w # 현재 정점까지의 가중치 + 다음 정점까지의 가중치
                if cost < distance[v]: # 현재 정점까지의 가중치가 더 작다면
                    distance[v] = cost
                    heapq.heappush(queue,(cost,v))

    dijkstra(K)

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


if __name__ == '__main__':
    main()

 

해설

• 그래프탐색, 다익스트라, 최소힙

최단경로를 구하는 다익스트라 알고리즘으로 풀 수 있는 전형적인 문제입니다.

단, 노드(정점)의 개수가 최대 20,000개이므로 최소힙을 사용하지 않으면 시간 초과 판정을 받게 설계가 되어 있을 것입니다..!

따라서 최소힙을 사용하여 현재 노드를 기준으로 이동할 수 있는 거리가 가장 짧은 것을 먼저 불러와 처리해야 합니다.

구체적인 내용은 아래에 설명하겠습니다 😃

 

그래프, 거리 리스트 초기화

노드(정점)의 개수 V보다 1 더 큰 숫자로 그래프와 거리 리스트를 초기화해줍니다.

그 이유는 다들 아시겠지만 우리가 사용하는 노드의 번호를 곧 인덱스로 사용하기 위함입니다.

이때 거리는 INF라는 변수로 초기화하는데, 일반적으로 어떻게 해도 이것보다 큰 값이 나오기 쉽지 않게 세팅해두는 것입니다.

위에서는 1e9(10억)으로 초기화했습니다.

(시작점으로부터 거리가 아무리 멀어도 10억까지는 쉽지 않겠죠)

INF = int(1e9) # 초기값
graph = [[] for _ in range(V+1)]
distance = [INF] * (V+1)

for _ in range(E):
    u,v,w = map(int,sys.stdin.readline().strip().split())
    graph[u].append((v,w)) # (정점, 가중치)

 

최소힙을 이용한 다익스트라

혹시 최소힙이 무엇인지 모르시는 분이 계실까봐 아주 간단히만 설명하겠습니다.

힙이라는 자료구조는 이진 탐색을 통해 아주 빠르게 최솟값을 뽑아낼 수 있도록 설계된 자료구조입니다.

따라서 heappush 함수를 사용하면 해당 값을 리스트 내 적당한 위치에 집어넣고,

heappop 함수를 사용하면 해당 리스트에서 최솟값을 뽑아준다, 정도로 이해하시면 되겠습니다.

 

우선 시작점의 거리는 0으로 설정해주고 heappush를 이용하여 queue를 만들어줍니다.

이때 queue에 들어가는 원소는 (지금까지의 비용, 도착점) 이 됩니다.

def dijkstra(start): # 최단경로 탐색
    queue = []
    heapq.heappush(queue,(0,start)) # (가중치, 정점)
    distance[start] = 0

 

이후 과정은 BFS와 굉장히 유사하죠!

큐가 빌 때까지, 즉 더이상 이동할 노드가 없을 때까지 과정을 반복합니다.

이때 가중치를 기준으로 가장 작은 원소를 하나 꺼내어 dist, now 변수에 값을 할당합니다.

dist는 말 그대로 가중치(지금까지의 비용)이 되고, now는 현재 확인할 노드(정점)가 됩니다.

 

만약 distance 리스트에 현재 확인하고자 하는 노드의 값이, 지금까지 이동하는 데 드는 비용보다 작다면 우리는 굳이 값을 갱신할 필요가 없습니다.

즉, 다른 경로를 통해 해당 노드로 이동하는 것이 최단 경로가 되는 것이죠.

그래서 이 조건에 해당되는 경우엔 굳이 확인할 필요 없이 continue를 이용하여 다른 노드를 탐색합니다.

dist,now = heapq.heappop(queue)
if distance[now] < dist: # 최단 경로가 아니라면
    continue

 

만약 위 조건에 해당하지 않는다면, 즉 현재 노드에 대한 추가 탐색을 진행하는 것이 최단 경로라면 graph를 통해 다음 노드와 가중치를 받아옵니다.

이는 v,w 라는 변수에 값을 받아오도록 하구요!

 

이때 현재 노드에서 다음 노드로 이용할 때의 총 비용은, 지금까지의 비용(dist) + 현재 이동할 때 드는 비용(w)가 될 것입니다.

이를 cost라는 변수에 담아줍니다.

이제 cost가 distance 리스트 내 이동하고자 하는 노드(v)의 값보다 작다면 우리는 값을 갱신해주면 됩니다.

이 과정이 존재하기 때문에 그래프를 초기화할 때 두 노드 사이에 여러 개의 간선이 존재하더라도 굳이 필터링할 필요가 없는 것입니다.

 

그리고 이 조건을 만족하는 가중치와 노드의 경우 튜플 형태로 다시 큐에 push 해줍니다.

for v,w in graph[now]:
    cost = dist + w # 현재 정점까지의 가중치 + 다음 정점까지의 가중치
    if cost < distance[v]: # 현재 정점까지의 가중치가 더 작다면
        distance[v] = cost
        heapq.heappush(queue,(cost,v))

 

마지막으로 distance 리스트에 저장된 값을 확인하면서 INF 또는 최단 경로 비용을 출력해주면 정답이 됩니다.