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

문제 출처 : https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

문제 확인

이 문제는 제목에서 알 수 있듯이 최소 비용 구하기 문제와 거의 비슷합니다. 다른점 이라면 이동한 경로를 표시해야 한다는 점입니다. 이동하는 경로를 어떻게 표시 하는지에 어려워 하는 친구들이 있어 그 부분에 대해 알려주기 위해 글을 남깁니다. 다익스트라 알고리즘으로 이 문제를 해결하기 위한다면 최소 비용 구하기부터 확인 하시기 바랍니다.

01. 최소 비용 구하기[백준 1916]

01. 최소 비용 구하기[백준 1916]

경로를 구하는 방법

이동한 경로를 구하는 방법은 여러가지가 있겠지만 여기서 소개하는 방법은 두가지 입니다. 첫 번째 방법은 경로를 우선순위 큐에 같이 넣는 방법 입니다. 두 번째 방법은 경로를 표시할 배열을 하나 만드는 것입니다. 어떤 방법을 사용해도 상관 없습니다. 다만 첫 번째 방법은 단순하고 쉽지만 메모리를 많이 잡아 먹습니다. 경로가 너무 많아지는 경우에는 이 방법이 좋지 않을 수 있습니다. 두 번째 방법은 경로에 대한 배열이 하나만 추가되기 때문에 메모리를 많이 잡아먹지는 않지만 나중에 배열에서 경로만 추출하는 로직이 추가적으로 필요합니다. 또 같은 곳을 두 번 이상 방문해야 하는 문제에서는 이 방법을 사용할 수 없습니다. 경로를 하나만 기억하기 때문 입니다. 두 번 이상 같은 곳을 방문하는 경우에는 좀 더 응용해서 문제를 해결해야 합니다. 따라서 두 가지 경우 모두 알아두었다가 문제에 맞게 활용하기를 바랍니다.

기본 코드 작성

먼저 기본적인 다익스트라 알고리즘으로 작성된 코드 입니다. 코드의 내용이 이해되지 않는다면 위의 링크를 통해 최소 비용 구하기 설명을 확인하시기 바랍니다.

from heapq import heappop, heappush

mii = lambda : map(int, input().split())
N = int(input())
M = int(input())

arr = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, w = mii()
    arr[u].append((w, v))

start, end = mii()
INF = float("INF")
dist = [INF] * (N + 1)

def dijkstra(S):
    visited = [False] * (N + 1)    
    dist[S] = 0
    q = [(0, S)]

    while q:
        cur_dist, cur_node = heappop(q)

        if visited[cur_node]:
            continue
        
        visited[cur_node] = True
        for nxt_dist, nxt_node in arr[cur_node]:
            distance = cur_dist + nxt_dist

            if distance < dist[nxt_node]:
                dist[nxt_node] = distance
                heappush(q, (distance, nxt_node))

dijkstra(start)
print(dist[end)

큐에 경로를 기억하는 방법

먼저 큐에 경로를 추가하는 방법에 대해 알아보겠습니다. 현재 큐에는 거리와 현재 노드만 들어가 있습니다. 여기에 경로를 추가하는 것입니다. 먼저 큐를 선언할 때 첫 번째 경로를 추가해 줍니다.

def dijkstra(S, E):
    visited = [False] * (N + 1)    
    dist[S] = 0
    q = [(0, S, [S])]

다익스트라 알고리즘을 시작할 때 시작인 S뿐만 아니라 끝인 E까지 모두 입력 받습니다. 큐는 모든 반복이 완료되면 아무것도 남지 않기 때문에 도착지점에 도착하면 현재 경로를 리턴하기 위해서 입니다.

큐에서 꺼낼 때에도 거리와 정점뿐만 아니라 경로를 같이 꺼내옵니다.

    while q:
        cur_dist, cur_node, path = heappop(q)

그리고 현재 노드가 도착지점이 되었을 때 그 경로를 리턴 합니다.

        if visited[cur_node]:
            continue

        if cur_node == E:
            return path

경로를 리턴하기 때문에 다익스트라 알고리즘을 완료하고 경로를 리턴 받는 부분을 추가해 주어야 합니다.

마지막으로 큐에 거리와 정점을 추가할 때 경로도 같이 추가해 줍니다.

            if distance < dist[nxt_node]:
                dist[nxt_node] = distance
                heappush(q, (distance, nxt_node, path + [nxt_node]))

첫 번째 방법의 전체 코드

그럼 첫 번째 방법의 전체 코드를 확인해 보겠습니다.

from heapq import heappop, heappush

mii = lambda : map(int, input().split())
N = int(input())
M = int(input())

arr = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, w = mii()
    arr[u].append((w, v))

start, end = mii()
INF = float("INF")
dist = [INF] * (N + 1)

def dijkstra(S, E):
    visited = [False] * (N + 1)    
    dist[S] = 0
    q = [(0, S, [S])]

    while q:
        cur_dist, cur_node, path = heappop(q)

        if visited[cur_node]:
            continue

        if cur_node == E:
            return path
        
        visited[cur_node] = True
        for nxt_dist, nxt_node in arr[cur_node]:
            distance = cur_dist + nxt_dist

            if distance < dist[nxt_node]:
                dist[nxt_node] = distance
                heappush(q, (distance, nxt_node, path + [nxt_node]))

path = dijkstra(start, end)

print(dist[end])
print(len(path))
print(*path)

경로 기억하기 두 번째 방법

경로를 기억하는 두 번째 방법을 알아보겠습니다. 거리를 기억할 path라는 배열을 하나 만들어 줍니다.

INF = float("INF")
dist = [INF] * (N + 1)
path = [-1] * (N + 1)

시작 거리의 값을 만들 때 같이 최초 경로를 만들어 줍니다.

    # 시작값
    dist[S] = 0
    path[S] = 0

그리고 경로를 큐에 넣을 때 path 값을 업데이트 합니다.

            if distance < dist[nxt_node]:
                dist[nxt_node] = distance
                path[nxt_node] = cur_node
                heappush(q, (distance, nxt_node))

마지막으로 배열에 들어있는 경로를 하나의 리스트에 담아주는 로직을 구현합니다.

x = end
result = [end]
while path[x] != 0:
    x = path[x]
    result.append(x)

result에 마지막 위치인 end값이 들어 있습니다. 이 값을 시작으로 path를 거꾸로 가면서 위치를 찾는 것입니다. path[x]값이 0이 되면 아까 처음에 선언한 것처럼 시작값이 된 것이고, result에는 path값이 거꾸로 들어있을 것입니다. 이 result값을 뒤집어주면 경로를 얻을 수 있습니다.

두 번째 방법 전체 코드

두 번째 방법의 전체 코드를 확인해 보겠습니다.

from heapq import heappop, heappush

mii = lambda : map(int, input().split())
N = int(input())
M = int(input())

arr = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, w = mii()
    arr[u].append((w, v))

start, end = mii()

INF = float("INF")
dist = [INF] * (N + 1)
path = [-1] * (N + 1)

def dijkstra(S):
    visited = [False] * (N + 1)
    
    # 시작값
    dist[S] = 0
    path[S] = 0

    q = [(0, S)]

    # 반복 시작
    while q:
        cur_dist, cur_node = heappop(q)

        # 방문 확인
        if visited[cur_node]:
            continue

        visited[cur_node] = True
        # 노드 순회
        for nxt_dist, nxt_node in arr[cur_node]:
            distance = cur_dist + nxt_dist

            if distance < dist[nxt_node]:
                dist[nxt_node] = distance
                path[nxt_node] = cur_node
                heappush(q, (distance, nxt_node))

dijkstra(start)

x = end
result = [end]
while path[x] != 0:
    x = path[x]
    result.append(x)

print(dist[end])
print(len(result))
print(*result[::-1])