[파이썬] 백준 1719번 택배

백준 #1719 택배

• 백준 1719번 택배 문제풀기

• 모든 집하장에서 각각 다른 집하장으로 가는 최단 경로를 구해야 한다.
• 출력: 가장 먼저 가야하는 집하장 경로표 (자신에게 가는 건 - 로 표시)

1. 플로이드 알고리즘 (플로이드-워셜)

# 모든 쌍에 대한 최단 경로를 구해야 하므로 플로이드 알고리즘을 사용한다.
# 1. 가중치 field
# 2. 초기 간선 연결 여부 edges
# 3. 경로표 table

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
field = [[float('inf') for i in range(n+1)] for j in range(n+1)]
edges = [[0 for i in range(n+1)] for j in range(n+1)]
table = [['-' for i in range(n+1)] for j in range(n+1)]

for i in range(1, n+1):
    for j in range(i, n+1):
        if i != j:
            table[i][j] = j
            table[j][i] = i

for _ in range(m):
    s, e, t = map(int, input().split())
    field[s][e] = t
    field[e][s] = t
    edges[s][e] = 1
    edges[e][s] = 1

for i in range(1, n+1):
    field[i][i] = 0

for k in range(1, n+1):
    for i in range(1, n+1):
        if field[i][k]:
            for j in range(1, n+1):
                if field[i][j] > field[i][k] + field[k][j]:
                    field[i][j] = field[i][k] + field[k][j]
                    table[i][j] = k

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j: continue
        arrive = table[i][j]
        while not table[i][arrive] == arrive:
            arrive = table[i][arrive]
        table[i][j] = arrive

for _ in range(1, n+1):
    print(*table[_][1:])

• 2168 ms
• 플로이드 알고리즘은 최단 ‘거리’ 알고리즘이다.
  • 경로를 찾을 땐 추가적인 작업이 필요하다.

2. 다익스트라 알고리즘

# 다익스트라 알고리즘을 모든 집하장에 대해 실행하고, 
# 맨 처음 방문하는 집하장을 경로표에 모은다.

import sys
input = sys.stdin.readline


def Dijkstra(G, s, n):
    visited = [0 for i in range(n+1)]
    dist = [float('inf') for i in range(n+1)]
    parents = ['-' for i in range(n+1)]
    dist[s] = 0

    for i in range(1, n+1):
        minidx, minval = -1, float('inf')
        for j in range(1, n+1):
            if not visited[j] and dist[j] < minval:
                minidx = j
                minval = dist[j]
        visited[minidx] = 1

        if G.get(minidx):
            for v, val in G.get(minidx):
                if not visited[v] and dist[minidx] + val < dist[v]:
                    dist[v] = dist[minidx] + val
                    parents[v] = minidx
                    if minidx == s: parents[v] = v
    
    for i in range(1, n+1):
        if i == s: continue
        arrive = parents[i]
        while not parents[arrive] == arrive:
            arrive = parents[arrive]
        parents[i] = arrive

    return parents[1:]

n, m = map(int, input().split())
graph = dict()
result = []

for i in range(m):
    s, e, t = map(int, input().split())
    if graph.get(s):
        graph.get(s).append((e, t))
    else:
        graph[s] = [(e, t)]
    if graph.get(e):
        graph.get(e).append((s, t))
    else:
        graph[e] = [(s, t)]

for i in range(1, n+1):
    result.append(Dijkstra(graph, i, n))

for _ in range(n):
    print(*result[_])

• 1016 ms

• 집하장의 개수를 V, 경로의 개수를 E라고 한다면 위의 구현 방식에서

  • 플로이드-워셜 알고리즘의 시간 복잡도는 O(V³)
  • 다익스트라 알고리즘의 시간 복잡도는 O(V²+E)이다.

  이런 이유로 플로이드-워셜 알고리즘을 사용한 코드가 다익스트라 알고리즘을 사용한 코드보다 연산 시간이 더 길어졌다고 볼 수 있다.