[Python] 백준 11779 최소비용 구하기 2

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

 

문제 분석

• n개의 도시
• 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스
• A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화하려고 할 때,
• A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용과 경로를 출력하라
  
  
• bus[출발지] = [도착지, 비용]

 

코드 설계

• 다익스트라
  
  
• 모든 거리에 대한 비용을 1e9로 초기화
• 시작위치에 대한 비용은 0
• 만약 이전 비용에 대해 현재 노드 + 가중치가 작으면 갱신 : 새로운 경로
  
  
• 어떻게 최소 비용을 갖는 경로를 방문하는 도시를 알 수 있을까
• https://kau-algorithm.tistory.com/1566

 

정답 코드

1차 실패

다른 정답 코드 1

import sys, heapq

input = sys.stdin.readline

n = int(input())
m = int(input())

bus = [[] for _ in range(n+1)]
for _ in range(m) :
    start, end, weight = map(int, input().split())
    bus[start].append([weight, end])

a, b = map(int, input().split())

h = []
heapq.heappush(h, (0, a)) # 시작위치에서 시작위치로 가는 비용은 0

route = [1e9 for _ in range(n+1)] # 각 도시에 대해 갈 수 있는 비용 (최댓값으로 초기화)
route[a] = 0

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

while h :
    dist, now_node = heapq.heappop(h) # 현재 위치까지의 비용, 현재 위치

    if now_node == b :
        break

    for i in range(len(bus[now_node])) :
        next_node = bus[now_node][i][1]
        weight = bus[now_node][i][0]

        if route[now_node] + weight < route[next_node] :
            route[next_node] = route[now_node] + weight
            heapq.heappush(h, (dist+weight, next_node))
            prev_node[next_node] = now_node

path = [b]
now = b

while now != a :
    now = prev_node[now]
    path.append(now)

print(route[b])
path.reverse()
print(len(path))
print(' '.join(map(str, path)))

 

 

2회차 - 25.05.27

1차 : 출발지에서 도착지까지의 최소 비용

import sys, heapq
input = sys.stdin.readline

n = int(input()) # 도시
m = int(input()) # 버스
bus = [[] for _ in range(m+1)]

for _ in range(m) :
    start, end, weight = map(int, input().split())
    bus[start].append([weight, end])
s, e = map(int, input().split())

# 출발 지점으로부터 도착했을 때의 최소 경로 저장
distance = [1e9 for _ in range(n+1)]
distance[s] = 0

path = []
h = []
# 시작 위치에서 출발 : 출발 위치에 대한 비용은 0
heapq.heappush(h, (0, s))

while h:
    w, node = heapq.heappop(h) # 현재 위치

    # 현재 위치에서 갈 수 있는 다음 위치들에 대해 업데이트 가능한지 -
    for i in range(len(bus[node])) :
        next_node = bus[node][i][1] # 다음 위치
        new_weight = w + bus[node][i][0] # 현재 위치에서 다음 위치로 이동하는 비용

        # 현재 위치에서 이동할 수 있는 거리 중 값이 더 작다면 갱신
        if new_weight < distance[next_node] :
            distance[next_node] = new_weight
            heapq.heappush(h, (new_weight, next_node))

print(distance[e])

 

최소 비용을 갖는 거리

• 비용이 업데이트 되면 업데이트 되기 전에 경로 저장 (이전, 이동 경로)

import sys, heapq
input = sys.stdin.readline

n = int(input()) # 도시
m = int(input()) # 버스
bus = [[] for _ in range(n+1)]

for _ in range(m) :
    start, end, weight = map(int, input().split())
    bus[start].append([weight, end])
s, e = map(int, input().split())

# 출발 지점으로부터 도착했을 때의 최소 경로 저장
distance = [1e9 for _ in range(n+1)]
distance[s] = 0

pre_node = [0 for _ in range(n+1)]
h = []
# 시작 위치에서 출발 : 출발 위치에 대한 비용은 0
heapq.heappush(h, (0, s))

while h:
    w, node = heapq.heappop(h) # 현재 위치

    if node == e :
        break

    # 현재 위치에서 갈 수 있는 다음 위치들에 대해 업데이트 가능한지 -
    for i in range(len(bus[node])) :
        next_node = bus[node][i][1] # 다음 위치
        new_weight = w + bus[node][i][0] # 현재 위치에서 다음 위치로 이동하는 비용

        # 현재 위치에서 이동할 수 있는 거리 중 값이 더 작다면 갱신
        if new_weight < distance[next_node] :
            distance[next_node] = new_weight
            heapq.heappush(h, (new_weight, next_node))
            pre_node[next_node] = node

# 거꾸로 확인하면서 이동 경로 찾기
path = [e]
now = e

while now != s :
    now = pre_node[now]
    path.append(now)

path.reverse()

print(distance[e])
print(len(path))
print(" ".join(map(str, path)))