[Python] 백준 1916: 최소비용 구하기

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

1916번: 최소비용 구하기

1. 다익스트라 알고리즘을 이용한다.

2. 시작정점에서 모든 정점 방문후, 시작정점에서 각 정점마다 가장 짧은 비용을 출력한다.

3. 두 정점간의 여러가지 경로값이 주어질수도 있다. 그래서 매 경로마다 최솟값을 갱신해줘야한다.

 

 

아래는 배열을 이용한 다익스트라 알고리즘인데 정점마다 모든정점을 확인해야하기 때문에 O(V^2) 시간이 드는데 이는 정점이 많고 간선이 적을때 매우 비효율적이다. 그래서 밑의 우선순위 큐를 이용하면 더 빠른 알고리즘이 된다.

 

INF = 100000001
n = int(input())
m = int(input())
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
d = [INF for _ in range(n+1)]
visit = [False for _ in range(n+1)]


def minIndex():
    minValue = INF
    idx = 0
    for i in range(1, n+1):
        if not visit[i] and minValue > d[i]:
            minValue = d[i]
            idx = i
    return idx


def dijkstra(x):
    for i in range(1, n+1):
        d[i] = graph[x][i]
    visit[x] = True

    for _ in range(n-2):
        x = minIndex()
        visit[x] = True
        for i in range(1, n+1):
            if not visit[i] and graph[x][i] + d[x] < d[i]:
                d[i] = graph[x][i] + d[x]
    print(d[e])


for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)

s, e = map(int, input().split())

dijkstra(s)

 

우선순위큐를 이용한 다익스트라 알고리즘이다. 인접한 정점노드를 확인하는데 O(E) 가장 작은 노드를 찾는데 O(logE)(힙구조의 데이터를 넣을때 시간복잡도 logE 뺄때 logE 2logE인데 상수는 버리므로 logE)

O(ElogE)의 시간복잡도를 다진다.

 

from heapq import heappush, heappop

INF = 100000001
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
d = [INF for _ in range(n+1)]
visit = [False for _ in range(n+1)]


def dijkstra(s, e):
    heap = []

    d[s] = 0
    heappush(heap, [0, s])
    while heap:
        cur = heappop(heap)[1]
        if visit[cur]:
            continue

        visit[cur] = True
        for next, dis in graph[cur]:
            cost = d[cur] + dis
            if not visit[next] and cost < d[next]:
                d[next] = cost
                heappush(heap, (cost, next))

    print(d[e])


for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])

s, e = map(int, input().split())

dijkstra(s, e)