[BOJ 1719] : 택배

문제 링크 : https://www.acmicpc.net/problem/1719

1719번: 택배

 1753번처럼 한 노드에서 다른 노드들까지의 최단거리를 찾되, 모든 노드에 대해 이를 반복해 풀 수 있는 문제입니다.
다만 두 가지 함정이 숨어 있었는데요, 한번 천천히 알아보도록 하겠습니다.

---

이번 답안은 다익스트라 입문 문제인 1753번 코드를 많이 참고하면서 완성했는데요, 첫 번째 함정은 이번 문제는 그래프가 양방향 그래프가 된다는 것입니다.

1753번에서는 단순히 한 노드에서 다른 노드들로 이동하는 단방향 탐색을 수행하기 때문에 아래처럼 그래프를 단방향으로 구성할 수 있었지만, 이번 문제에서는 2번 노드에서 6번 노드로 이동이 가능했다면, 6번 노드에서 2번 노드로도 탐색이 가능하도록 코드를 수정해야 합니다.

[기존 단방향 그래프 생성 코드]

for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((w, v))

[수정된 양방향 그래프 생성 코드]

for i in range(M):
    src, dist, weight = map(int, input().split())
    graph[src].append((dist, weight))
    graph[dist].append((src, weight))

'무슨 이게 함정이야' 라고 하실수도 있겠지만, 저는 이걸 알아내고 매우 기뻐했습니다.
아무튼, 두 번째 함정입니다.

이번 문제에서는 최단거리의 테이블을 만드는데, 테이블의 내용은 최단거리가 아닌 이전에 어떤 노드를 거쳤는지 가 되어야 합니다.
사실 여기부터는 스스로 생각하지 못했는데요, 신기하게도 가중치의 리스트의 행과 열을 뒤집고, 현재 선택한 노드를 거기에 대입하는 식으로 테이블을 완성하면 방문한 노드들이 담긴 테이블이 완성됩니다.

def dijkstra(startNode):
    weightList[startNode][startNode] = 0
    heapq.heappush(heap, (0, startNode))

    while heap:
        weight, current = heapq.heappop(heap)
        if weightList[startNode][current] < weight:
            continue

        for _next, _weight in graph[current]:
            nextWeight = weight + _weight
            if nextWeight < weightList[startNode][_next]:
                weightList[startNode][_next] = nextWeight
                heapq.heappush(heap, (nextWeight, _next))
                # 방문한 노드의 위치가 담기는 테이블
                d[_next][startNode] = current

다만 이게 어떻게 되는건지는 아직 잘 머리에 그려지지 않아서............
비슷한 유형의 문제를 조금 풀어봐야 할 것 같습니다..

마지막으로, 완성된 코드입니다.

import heapq
import sys

input = sys.stdin.readline
INF = sys.maxsize

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
weightList = [[INF] * (N + 1) for _ in range(N + 1)]
visited = [[0] * (N + 1) for _ in range(N + 1)]
heap = []

for i in range(M):
    src, dist, weight = map(int, input().split())
    graph[src].append((dist, weight))
    graph[dist].append((src, weight))


def dijkstra(startNode):
    weightList[startNode][startNode] = 0
    heapq.heappush(heap, (0, startNode))

    while heap:
        weight, current = heapq.heappop(heap)
        if weightList[startNode][current] < weight:
            continue

        for _next, _weight in graph[current]:
            nextWeight = weight + _weight
            if nextWeight < weightList[startNode][_next]:
                weightList[startNode][_next] = nextWeight
                heapq.heappush(heap, (nextWeight, _next))
                visited[_next][startNode] = current


for i in range(1, N + 1):
    dijkstra(i)

for row in range(1, N + 1):
    for col in range(1, N + 1):
        if visited[row][col] == 0:
            print("-", end=" ")
        else:
            print(visited[row][col], end=" ")
    print()