[백준BOJ] 11779번 최소비용 구하기2.py

 

백준 저지에서 최소비용 구하기2를 파이썬을 통해 풀어 보았다. 

 

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

11779번: 최소비용 구하기 2

11779번 최소비용 구하기2.py

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1259번 팰린드롬수

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화시키려고 한다. 그러면 A번째 도시에서 B번째 도시까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

설명

다익스트라를 통해서 풀 수 있는 문제이다. 문제풀이에 앞서 다익스트라에 대해서 알아보자.

 

다익스트라는 하나의 노드에서 모든 노드로 가는 최소 비용을 구하는 알고리즘이다. 가중치가 존재하는 방향 그래프가 주어지면 사용할 수 있다. 다익스트라는 다음 과정을 거친다.

 

1. 출발점을 선정
2. heap에 있는 노드 중 가장 적은 가중치를 가진 노드를 선택
3. 선택한 노드를 거쳐 다른 노드로 가는 가중치 계산
4. 계산한 가중치가 기존에 저장했던 가중치보다 작다면 갱신 + heap에 삽입
5. 2~5 반복

다익스트라 알고리즘은 순차적으로 탐색하지 않는다. heap에 있는 노드 중 가중치가 가장 작은 노드를 선택하기 때문에 그리드 알고리즘으로도 분류된다.

 

문제에서는 시작 지점과 도착 지점을 정해놨으며 경로까지 출력해야 한다. 각 지점까지 가중치를 저장하는 costs 배열과 경로를 저장하는 root 배열을 선언한다. 만약 힙에 노드를 삽입해야 하는 상황이 온다면, 즉 새로 계산한 가중치가 기존에 저장한 가중치보다 크다면 가중치 갱신과 함께 경로도 갱신해야 한다. 

 

만약 a->b라면 a까지 경로에 a->b를 추가하여 b 경로에 갱신하면 된다.

코드

#11779번 최소비용 구하기2.py
import sys
import heapq
import math
input = sys.stdin.readline

def dijkstra(start,buses,costs,root) : 
    q=[]
    root[start]=[start] #시작 경로 설정
    costs[start]=0
    heapq.heappush(q,(0,start,root[start])) #heap에 비용, 출발 노드, 경로 저장

    while q :
        cost, now, root_to_now = heapq.heappop(q) #가장 작은 가중치를 가진 노드 선택->현재 위치
        if costs[now] < cost : #선택한 노드의 가중치가, 이미 저장된 선택한 노드까지의 가중치보다 크다면 
            continue
        for bus in buses[now] : 
            next_cost = cost+bus[1] #now에서 버스를 타고 "다음 노드"로 가는 가중치 계산
            if next_cost < costs[bus[0]] : #가중치가 "이미 저장된 다음 노드로 가는 가중치" 보다 작다면
                costs[bus[0]]=next_cost #"다음노드"로 가는 가중치 갱신
                root[bus[0]] = root_to_now+[bus[0]]#경로도 갱신
                heapq.heappush(q,(next_cost,bus[0],root[bus[0]]))#heap에 추가
        

if __name__ == "__main__" :
    n = int(input())
    m = int(input())
    buses = [[]for _ in range(n+1)]
    for i in range(m):
        start, end, cost = map(int,input().split())
        buses[start].append([end,cost])
    
    costs = [int(1e9)]*(n+1)
    start, end = map(int,input().split())
    root=[[]for _ in range(n+1)]

    dijkstra(start,buses,costs,root)
    print(costs[end])
    print(len(root[end]))
    print(" ".join(map(str,root[end])))