[Python] 백준 1719 - 택배 문제 풀이

Overview

BOJ 1719번 택배 Python 문제 풀이
분류: Shortest Path (최단거리)

---

문제 페이지

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

---

풀이 코드 1 - 플로이드 와샬 알고리즘

from sys import stdin
from typing import List


INF = 10001


# 플로이드 와샬 알고리즘
def floyd_warshall(n: int, dists: List[List[int]], res: List[List[str]]) -> List[List[str]]:
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                # 자기 자신으로 가는 경로는 제외
                if i == j:
                    continue
                # k를 우회할 때 최단거리가 되는 경우
                if dists[i][j] > dists[i][k] + dists[k][j]:
                    dists[i][j] = dists[i][k] + dists[k][j]
                    # k로 가기 위한 첫 번째 집하장을 저장
                    res[i][j] = res[i][k]
    return res


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

    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)

    res = floyd_warshall(n, dists, res)

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


if __name__ == "__main__":
    main()

Floyd Warshall Algorithm을 이용한 풀이.
dists 리스트에 각 노드 별 최단 거리를 저장하고, res 리스트에는 최단 경로의 첫 번째 집하장을 저장한다.

---

풀이 코드 2 - 다익스트라 알고리즘

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()

Dijkstra Algorithm을 이용한 풀이.
각 지점 별로 다익스트라 알고리즘을 수행하여 최단 거리와 경로를 구한다.
dists 리스트에 각 노드 별 최단 거리를 저장하고, res 리스트에는 최단 경로의 첫 번째 집하장을 저장한다.