[백준] 1916번 최소비용 구하기(다익스트라 알고리즘)(Python - 파이썬)

백준 1916번 문제입니다. (solved.ac)기준 골드 5 문제입니다.

문제 접근

[백준] 1753번 최단경로(다익스트라 알고리즘)(Python)

위의 문제와 마찬가지로 다익스트라 알고리즘으로 간단하게 최소 비용을 구할 수 있는 문제입니다.

위의 문제와 다른 점은 1916번 문제는 노드의 수(N)가 최대 1,000개이기 때문에 이 문제는 우선순위 큐를 사용하지 않는,

시간복잡도가 O(N^2)인 간단한 다익스트라 알고리즘은로도 문제를 해결할 수 있습니다.

간단한 다익스트라 알고리즘은 

1. 출발 노드(start)를 설정

2. 최단 거리 테이블(distance)을 int(1e9)로 설정(노드 수 만큼)

3. 방문하지 않은 노드(visited = False) 중 최단 거리(distance)가 가장 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

5. 전체 노드를 방문처리할 때 까지 3, 4번을 반복

최소 비용을 최단 거리라고 생각하고 간단한 다익스트라 알고리즘을 사용하여 문제를 해결하였습니다!

 

정답 코드(간단한 다익스트라 알고리즘[O(N^2)])

import sys
input = sys.stdin.readline
INF = int(1e9)

# 도시의 개수(n) - 노드
# 버스의 개수(m) - 간선
n = int(input())
m = int(input())

# 방문처리를 판별할 것임
visited = [False] * (n+1)

# 버스비용을 거리라고 생각할 것임.
# 최단 거리(최소 비용) 테이블을 INF(10억)으로 초기화
distance = [INF] * (n+1)

graph = [[] for _ in range(n+1)]

# 그래프의 정보를 입력 받음(도시, 버스)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))

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

# 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
def get_short() :

    min = INF
    index = 0
    for i in range(1, n+1) :
        if distance[i] < min and visited[i] == False :
            min = distance[i]
            index = i

    return index

# 우선 순위 큐를 사용하지않는 간단한 다익스트라 알고리즘
# 시간복잡도 : O(N^2)
def dijkstra(start) :

    # 출발 도시에서 출발 도시로 가는 거리는 0
    distance[start] = 0
    # 출발 도시 방문처리
    visited[start] = True

    # 출발 도시와 연결되어있는 도시들을 순차적으로 탐색
    # 최단 거리(distance)보다 더 거리가 짧다면 갱신
    for j in graph[start] :
        if distance[j[0]] > j[1]:
            distance[j[0]] = j[1]

    # 모든 노드를 방문하면서 최단 거리 갱신 과정을 반복
    for i in range(n-1) :
        now = get_short()
        visited[now] = True

        for j in graph[now] :

            cost = distance[now] + j[1]

            if cost < distance[j[0]] :
                distance[j[0]] = cost

dijkstra(start)

print(distance[end])

정답 코드(개선된 다익스트라 알고리즘[O(mlogn)])

import sys
import heapq
INF = int(1e9)

# 도시의 개수(n) - 노드
# 버스의 개수(m) - 간선
n = int(input())
m = int(input())


# 버스비용을 거리라고 생각할 것임.
# 최단 거리(최소 비용) 테이블을 INF(10억)으로 초기화
distance = [INF] * (n+1)

graph =[[] for _ in range(n+1)]

# 그래프의 정보를 입력 받음(도시, 버스)
for i in range(1, m+1) :
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b,c))

# 출발점(start) - 출발 노드
# 도착점(end) - 도착 노드
start, end = map(int, sys.stdin.readline().split())

# 우선순위 큐를 이용한 개선된 다익스트라 알고리즘
# 시간 복잡도 : O(mlogn)
def dijkstra(start) :
    q = []

    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q :

        dis, now = heapq.heappop(q)
        
        # 이미 처리된 노드라면 무시
        if distance[now] < dis :
            continue

        for i in graph[now] :
            cost = dis + i[1]

            if cost < distance[i[0]] :
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


dijkstra(start)

print(distance[end])