새싹프로그래머의 이야기

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

문제: 도시 간 이동하는 버스 정보와 그 비용이 주어졌을 때, 출발 도시에서 도착 도시까지 드는 최소 비용 / 최소 비용을 갖는 경로에 있는 도시의 갯수 / 최소 비용을 갖는 경로로 방문하는 도시를 순서대로  출력하는 문제입니다.

풀이 방법: 다잌스트라 알고리즘

풀이 코드:

import sys
import heapq

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

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

for _ in range(m):
    startNode, endNode, cost = map(int,sys.stdin.readline().rstrip().split())

    graph[startNode].append((cost,endNode))

start, end = map(int,sys.stdin.readline().rstrip().split())

q = [(0,start)]
route = [[] for _ in range(n+1)]
distance = [1E9] * (n+1)
distance[start] = 0

while q:
    cost, node = heapq.heappop(q)

    if cost > distance[node]:
        continue
    for newCost, newNode in graph[node]:
        dist = newCost + distance[node]
        if dist < distance[newNode]:
            distance[newNode] = dist
            heapq.heappush(q,(distance[newNode],newNode))  # 위 코드 까지는 다잌스트라
            route[newNode] = [node] # 방문하는 경로 저장

pos = end
minRoute = [end]
while pos != start:
    minRoute.append(route[pos][0])
    pos = route[pos][0]

print(distance[end])
print(len(minRoute))
for i in minRoute[::-1]:
    print(i,end =' ')

풀이 설명:

for _ in range(m):
    startNode, endNode, cost = map(int,sys.stdin.readline().rstrip().split())

    graph[startNode].append((cost,endNode))

시작점과 도착점 정보로, 단방향성 정보가 주어집니다. 따라서 다음과 같이 그래프에 저장해주었습니다.

while q:
    cost, node = heapq.heappop(q)

    if cost > distance[node]:
        continue
    for newCost, newNode in graph[node]:
        dist = newCost + distance[node]
        if dist < distance[newNode]:
            distance[newNode] = dist
            heapq.heappush(q,(distance[newNode],newNode))  # 위 코드 까지는 다잌스트라
            route[newNode] = [node] # 방문하는 경로 저장

이제 코드에서 핵심되는 부분은 다잌스트라 알고리즘을 통해 최소 비용 및 방문하는 도시를 탐색하는 부분입니다. 

여기서 기존 다잌스트라 알고리즘과 다른 부분은 경로를 저장해주는 부분입니다.

route[newNode] = [node] # 방문하는 경로 저장

위 코드를 통해 최소 비용의 거리가 갱신되었을 경우 , 경로를 저장하도록 하였는데요. 

값을 append로 덧붙여 주는 것이 아닌 갱신 되었을 때 해당 값만 저장하도록 하여 최소 비용에 들어가는 도시만을 저장해였습니다.

예를 들어, 출발점과 도착점을  1 -> 2, 3 -> 4 가 있다고 하였을 때,

route[ 2 ] = [ 1 ] , route[ 4 ] = [ 3 ] 과 같은 형태로 저장되게 됩니다.

도착점에 대해 시작점의 정보를 value로 가질 수 있게 저장한 것입니다.

pos = end
minRoute = [end]
while pos != start:
    minRoute.append(route[pos][0])
    pos = route[pos][0]

저장한 경로를 바탕으로 위 코드를 통해 최소비용을 갖는 루트의 각 도시 정보를 구했습니다.

최소 비용을 갖는 루트가 1 -> 4 - > 5 라고 하였을 때,

route[ 5 ] =  [ 4 ]

route[ 4 ] = [ 1 ]  와 같이 저장이 되게 됩니다.

이를 도착점 부터 탐색하여 도착점 5를 통해 중간 도시인 4를, 중간 도시 4를 통해 시작 도시 1을 배열에 저장해줍니다.

print(distance[end])
print(len(minRoute))
for i in minRoute[::-1]:
    print(i,end =' ')

마지막으로 각 정보를 출력해주는데, 거쳐간 도시의 정보는 역순으로 저장해주었으므로 역순으로 출력해주었습니다.