[백준/파이썬] 1916번: 최소비용 구하기

문제

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

풀이

• 도시 개수 N, 버스 M대
• 각 버스는 출발 도시, 도착 도시, 비용
• 출발 도시 A에서 도착 도시 B까지 가는 데 최소 비용 출력

이 문제는 최소 비용 경로를 구하는 문제이며, 다익스트라 알고리즘을 이용해 해결할 수 있습니다.

🧐 다익스트라 알고리즘이란?

가중치가 있는 방향 또는 무방향 그래프에서 음의 가중치가 없을 때 사용할 수 있는 최단 경로 탐색 알고리즘

동작원리

1. 시작 노드의 거리는 0, 나머지는 무한대로 초기화
2. 가장 가까운 노드 선택
3. 그 노드를 거쳐서 갈 수 있는 이웃 노드들의 거리 갱신
4. 갱신한 거리 값이 더 짧으면 업데이트
5. 모든 노드를 처리할 때까지 반복

주의사항

• 음의 가중치가 있으면 사용할 수 없습니다 ‼️
  • 음의 가중치가 존재하는 경우 벨만포드 알고리즘 사용

---

if __name__ == "__main__":
    n = int(input())
    m = int(input())
    graph = [[] for _ in range(n+1)]

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

버스의 정보를 담을 graph에 출발 지점: 도착 지점, 비용 형태로 삽입

    start, target = map(int,input().split())
    distance = [1e9] * (n+1)

거리를 모두 무한대로 초기화해 줍니다.

이제 다익스트라 함수를 정의하겠습니다.

def func(start):
    queue = []
    heapq.heappush(queue, (0, start))
    distance[start] = 0

heapq에 비용과 도시 번호를 삽입
시작 도시는 비용을 0 처리

    while queue:
        dist, cur = heapq.heappop(queue)

가장 비용이 적은 노드를 꺼내 줍니다.

        if dist > distance[cur]:
            continue

만약 이미 더 짧은 경로로 처리된 경우는 무시

        for next, cost in graph[cur]:
            new_cost = dist + cost # 현재 노드를 거쳐가는 비용
            
            if new_cost < distance[next]:
                distance[next] = new_cost
                heapq.heappush(queue, (new_cost, next))

현재 노드와 연결된 이웃 노드를 확인합니다.

만약 더 짧은 경로가 존재한다면 비용을 갱신하고 heapq에 삽입합니다.

이 과정을 계속 반복하면 우리가 찾고 싶은 도착 지점의 최소 비용이 나오게 됩니다.

코드

import sys, heapq
input = sys.stdin.readline

def func(start):
    queue = []
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    
    while queue:
        dist, cur = heapq.heappop(queue)
        
        if dist > distance[cur]:
            continue
        
        for next, cost in graph[cur]:
            new_cost = dist + cost
            
            if new_cost < distance[next]:
                distance[next] = new_cost
                heapq.heappush(queue, (new_cost, next))


if __name__ == "__main__":
    n = int(input())
    m = int(input())
    graph = [[] for _ in range(n+1)]

    for _ in range(m):
        s,t,c = map(int,input().split())
        graph[s].append((t,c))
    
    start, target = map(int,input().split())
    distance = [1e9] * (n+1)

    func(start)
    print(distance[target])