[Python][백준 1719] 택배

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

1719번: 택배

---

/*
신경써야 할 부분은 바로 :
1. 플로이드 워셜을 통해 최단거리를 계산한다
2. 최단거리 계산을 위해 비교하며 가장 먼저 거쳐간 집하장을 저장한다.
3. 저장된 집하장 정보가 없다면 현재의 k값을 있다면 원래의 집하장 정보를 저장한다.
*/

---

import sys
input = sys.stdin.readline
 
INF = float('inf')

def floyd_warshall(graph):
    n = len(graph)
    # 최단 경로 행렬 초기화
    # 0 if i == j else
    dist = [[0 if i == j else graph[i][j] if graph[i][j] != 0 else INF for j in range(n)] for i in range(n)]
    route = [["-" if i == j else j if graph[i][j] != INF else -1 for j in range(n)] for i in range(n)]
    
    # 동적 프로그래밍을 통한 갱신
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    if route[i][k] == -1 :
                        route[i][j] = k
                    else : 
                        route[i][j] = route[i][k]

    return dist, route


v,e = map(int, input().split())
graph = [[INF for _ in range(v+1)] for _ in range(v+1)]

for i in range(e) :
    a,b,c = map(int, input().split())
    
    graph[a][a] = 0
    graph[b][b] = 0
    graph[a][b] = c
    graph[b][a] = c

shortest_paths,route = floyd_warshall(graph)

for i in range(1,v+1) :
    for j in range(1,v+1) :
        print(route[i][j], end=" ")
    print()

---

풀 때 어려웠던 점 또는 느낀점 :

그동안 풀었던 플로이드 워셜 문제들은 최단거리를 구하거나 단방향 그래프 였다면
이번 문제는 최단거리 구하는 것은 같지만 경로를 저장해서 그 경로를 출력하는 문제였다

처음 문제를 보자마자 뭘 요구하는지는 감이 왔고 그걸 코드로 옮기기만 하면 됐다.

그리 어려운 문제는 아니지만 이게 골3이라니...

최근에 플로이드 워셜만 풀고 있어 그렇게 느꼈을지도 모르겠다

이제 골2, 골1, 플레까지 플로이드 워셜 풀어보고 넘어가야겠다.

---

참고할만한 다른 사람 코드 :

from sys import stdin
from heapq import heappop, heappush


INF = 10001
dists, res = [], []


# 다익스트라 알고리즘
def dijkstra(start: int, n: int) -> None:
    global dists, res

    hq = []
    for i in range(1, n + 1):
        if i == start:
            continue
        heappush(hq, (dists[start][i], i))

    while hq:
        dist, node = heappop(hq)

        if dists[start][node] < dist:
            continue
        for neighbor in range(1, n + 1):
            # 자기 자신으로 가는 경로는 제외
            if node == neighbor or start == neighbor:
                continue
            # node를 우회할 때 start에서 neighbor 까지의 최단거리가 되는 경우
            if dist + dists[node][neighbor] < dists[start][neighbor]:
                dists[start][neighbor] = dist + dists[node][neighbor]
                heappush(hq, (dist + dists[node][neighbor], neighbor))
                # node로 가는 첫 번째 집하장을 neighbor 경로에 저장
                res[start][neighbor] = res[start][node]


def main():
    def input():
        return stdin.readline().rstrip()

    global dists, res

    n, m = map(int, input().split())
    dists = list(([INF] * (n + 1)) for _ in range(n + 1))
    res = [['-'] * (n + 1) for _ in range(n + 1)]

    for _ in range(m):
        a, b, w = map(int, input().split())
        dists[a][b] = dists[b][a] = w
        res[a][b] = str(b)
        res[b][a] = str(a)

    # 각 지점 별로 다익스트라 알고리즘 수행
    for i in range(1, n + 1):
        dijkstra(i, n)

    for line in res[1:]:
        print(*line[1:], sep=' ')


if __name__ == "__main__":
    main()

 

다익스트라 풀이다.

다익스트라 문제를 풀게 되면 참고해봐야겠다.