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

import sys
import heapq
input = sys.stdin.readline

N = int(input())
M = int(input())

graph = [{} for _ in range(N+1)]

parent_node = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')),pay)
    parent_node[y][x] = min(graph[y].get(x,float('inf')),pay)

INF = float('inf')
distance = [INF]*(N+1)

start_city,end_city = map(int,input().split())

distance[start_city] = 0
node_list = []
heapq.heappush(node_list,(0,start_city))

while node_list:
    cur_dis,cur_node = heapq.heappop(node_list)

    if distance[cur_node] < cur_dis:
        continue
    for next_node in graph[cur_node]:
        if distance[next_node] > cur_dis + graph[cur_node][next_node]:
            distance[next_node] = cur_dis + graph[cur_node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))


print(distance[end_city])
result = [end_city]
stack = [(distance[end_city],end_city)]
while stack:
    dis,cur_node = stack.pop()
    if cur_node == start_city:
        break
    for prev_node in parent_node[cur_node]:
        if graph[prev_node][cur_node] + distance[prev_node] == dis:
            stack.append((distance[prev_node],prev_node))
            result.append(prev_node)
            break

print(len(result))
result.reverse()
print(*result)
    

 

다익스트라를 이용해 푸는 문제이고, 경로를 추적해주면 되는 문제였다.

 

백준 5719번 문제 거의 최단경로에서 다익스트라 경로를 추적을 해본적이 있어서, 쉽게 풀수 있었다.

 

처음에 틀렸습니다를 받았는데, 경로를 추적하면서 출발점에 도착했을때, 반복문을 종료를 안시켜줘서 그렇다.

 

그 이유는 문제 조건 중에 pay가 0인경우가 있기때문에, 출발점을 넘어서 다른경로를 더 추적한 것 같다.

 

 

 

 

import sys
import heapq
input = sys.stdin.readline

N = int(input())
M = int(input())

graph = [{} for _ in range(N+1)]

path = [-1 for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')),pay)

INF = float('inf')
distance = [INF]*(N+1)

start_city,end_city = map(int,input().split())

distance[start_city] = 0
node_list = []
heapq.heappush(node_list,(0,start_city))

while node_list:
    cur_dis,cur_node = heapq.heappop(node_list)

    if distance[cur_node] < cur_dis:
        continue
    for next_node in graph[cur_node]:
        if distance[next_node] > cur_dis + graph[cur_node][next_node]:
            distance[next_node] = cur_dis + graph[cur_node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))
            path[next_node] = cur_node


print(distance[end_city])
result = []
city = end_city

while True:
    if city == start_city:
        result.append(city)
        break
    result.append(city)
    city = path[city]
print(len(result))
result.reverse()
print(*result)
    

 두번째 풀이는 위의 풀이보다 좀 더 깔끔한 풀이이다.  그 방식은 다익스트라를 하면서, 부모노드를 기록해주는 것이다.

 

최저 경로를 갱신해준 부모노드를 기록해주면, 최저의 비용으로 움직이는 하나의 경로를 저장할 수 있을것이다.

 

이걸 이용해서, start_city가 올때까지 반복문을 돌리는 방식으로 구현할 수 있다.

 

첫번째 풀이는, 모든 이동경로를 찾을때 쓰면 괜찮을 방법인것 같다.