[BOJ] 1916 : 최소비용 구하기 [그래프이론](Python)

문제 링크

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

1916번: 최소비용 구하기

소스 코드

import sys
from heapq import heappush, heappop

def main():
    n = int(input())
    m = int(input())
    graph = [[] for _ in range(n+1)]
    distance = [10**9] * (n+1) # 최댓값으로 초기화

    for _ in range(m):
        a, b, c = map(int, sys.stdin.readline().strip().split())
        graph[a].append((b,c)) # 출발, 도착, 비용

    start, end = map(int,input().split()) # 출발, 도착

    def dijkstra(start):
        queue = []
        distance[start] = 0 # 시작점 비용
        heappush(queue,(0,start))

        while queue:
            cost, x = heappop(queue) # 현재까지의 비용, 현재 노드
            if cost > distance[x]: # 현재까지의 비용이 더 크면 갱신 불필요
                continue

            for nx, ncost in graph[x]: # 이동 가능 노드, 추가 비용
                if cost + ncost < distance[nx]: # 현재까지 비용 + 추가 비용
                    distance[nx] = cost + ncost
                    heappush(queue, (distance[nx],nx)) # 비용기준 push
    
    dijkstra(start)
    print(distance[end])

if __name__ == '__main__':
    main()

 

해설

• 그래프이론, 다익스트라, 최단 경로

solved.ac의 클래스를 따라서 문제를 풀고 있는데 최단 경로 문제가 엄청나게 많네요 ㅋㅋㅋ

덕분에 최단 경로 알고리즘에 대해서는 많이 익숙해진 것 같습니다.

이 문제는 '간선의 가중치가 다를 수 있기 때문에' BFS가 아닌 다익스트라로 접근하는 것이 옳습니다.

(무조건 옳다는 없겠지만 방법도 훨씬 간편하고 효율적이기 때문입니다 😃)

 

시간복잡도

사실 지금까지 그래프에 관해서는 특히나 시간 복잡도 계산을 대충하고 넘어갔던 것 같은데 여러 번 보는만큼 확실히 짚고 넘어가겠습니다.

 

우선 다익스트라 알고리즘은 모든 노드(정점, V)를 한 번씩은 방문하게 됩니다.

(경우에 따라 그렇지 않을수도 있지만 항상 최악의 상황을 가정하죠)

그래서 이는 O(V)로 표현됩니다.

 

다음으로 노드를 중심으로 각 간선(E)들을 탐색하게 됩니다.

이때도 마찬가지로 최악의 경우에는 모든 간선을 탐색하게 되겠죠.

따라서 O(E)로 표현이 됩니다.

 

지금까지 노드와 각 노드별 간선에 대해 계산한 것이므로 둘을 더합니다.

(시간복잡도를 계산할 때는 둘 사이의 정확환 관계가 파악이 불가능하므로 곱셈으로 표현하는 것이 아님에 유의합니다)

따라서 지금까지 O(V+E)가 되었습니다.

 

이후 과정은 우선순위 큐를 활용합니다.

이때 우선순위 큐의 최대 길이는 노드(정점, V)의 개수입니다.

따라서 이 과정은 O(logV)가 됩니다.

이 과정은 위에서 계산한 모든 경우(O(V+E))마다 존재한다고 가정할 수 있습니다.

 

최종적으로 총 시간복잡도는 O((V+E)logV)가 됩니다.

우선순위 큐를 적용하지 않은 다익스트라 알고리즘의 시간복잡도는 O(V^2)이므로, 훨씬 효율적인 코드를 작성한 것임을 알 수 있습니다.

 

입력 및 그래프 초기화

아주 간단합니다.

양방향 간선이 아니므로 그래프에 (도착점, 비용) 을 묶어 추가합니다.

 

또한 시작점으로부터 각 노드(정점)로 이동할 때의 최소비용을 기록할 distance 리스트도 최댓값으로 초기화하여 만들어줍니다.

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
distance = [10**9] * (n+1) # 최댓값으로 초기화

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().strip().split())
    graph[a].append((b,c)) # 출발, 도착, 비용

start, end = map(int,input().split()) # 출발, 도착

 

우선순위 큐

시작점으로 이동하는 거리는 우선 0으로 바꿔줍니다.

 

그리고 '비용'을 중심으로 heappop, heappush를 수행합니다.

즉, 매 반복마다 처리하는 것은 '현재까지 이동한 비용'이 가장 작은 경우를 꺼내오는 것입니다.

또 '현재까지 이동한 비용 + 현재 추가된 비용'을 중심으로 queue에 집어 넣습니다.

이렇게 함으로써 해당 노드까지 이동하는 '최단 비용'을 구할 수 있게 됩니다.

 

반복문 안의 첫 번째 조건문은 처리할 필요가 없는 케이스들을 확인하는 과정입니다.

예를 들어 이전 계산을 통해 distance[1] = 10이라면, 현재 까지의 이동 비용이 12인 상황에서 굳이 계산할 필요는 없겠죠.

 

for문 아래의 조건문은 업데이트를 할지 말지 정하는 기준이 됩니다.

현재까지 이동했던 비용에 이동하면서 새로 생기는 비용을 더한 것이, distance에 저장된 것보다 작아야 최단 경로를 구하는 의미가 있겠죠.

따라서 이를 업데이트해주고 우선순위 큐에 다시 '비용'을 기준으로 삽입해주게 됩니다.

def dijkstra(start):
    queue = []
    distance[start] = 0 # 시작점 비용
    heappush(queue,(0,start))

    while queue:
        cost, x = heappop(queue) # 현재까지의 비용, 현재 노드
        if cost > distance[x]: # 현재까지의 비용이 더 크면 갱신 불필요
            continue

        for nx, ncost in graph[x]: # 이동 가능 노드, 추가 비용
            if cost + ncost < distance[nx]: # 현재까지 비용 + 추가 비용
                distance[nx] = cost + ncost
                heappush(queue, (distance[nx],nx)) # 비용기준 push

 

위 과정을 모두 마치고 distance 리스트에서 [end] 인덱스로 접근하여 정답을 출력하면 됩니다.