💻 백준 11404번: 플로이드

문제 소개 🧐

n개의 도시와 m개의 버스가 주어질 때, 모든 도시 쌍 (A, B)에 대해 도시 A에서 B로 가는 데 필요한 최소 비용을 구하는 문제입니다.

입력 📝

  • 첫째 줄: 도시의 개수 n (2 ≤ n ≤ 100)
  • 둘째 줄: 버스의 개수 m (1 ≤ m ≤ 100,000)
  • 셋째 줄부터 m개 줄: 버스 정보 (시작 도시 a, 도착 도시 b, 비용 c)

출력 📤

  • n개의 줄에 걸쳐 i번째 줄의 j번째 숫자는 도시 i에서 j로 가는 최소 비용을 출력합니다.
  • 갈 수 없는 경우는 0을 출력합니다.

제한 ❌

  • 시간 제한: 1초
  • 메모리 제한: 256MB

다익스트라 알고리즘 반복 적용 풀이 ✨

Idea

모든 도시에 대하여 dijkstra를 돌아보자.

문제는 모든 도시 쌍 간의 최단 경로를 요구하고 있다. 가장 먼저 떠오른 방법은, 하나의 시작점에서 다른 모든 점까지의 최단 경로를 구하는 다익스트라(Dijkstra) 알고리즘을 모든 도시에 대해 각각 실행하는 것이다. 즉, 1번 도시를 시작으로 다익스트라를 실행하고, 2번 도시를 시작으로 또 실행하고… n번 도시까지 반복한다.

Code

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((c, b))

def dijkstra(start, graph):
    q = []
    q.append((0, start))
    path = [float('inf')] * (n+1)
    path[start] = 0
    while q:
        cost, node = heapq.heappop(q)
    
        for n_cost, n_node in graph[node]:
            sum_cost = cost + n_cost
            if sum_cost < path[n_node]:
                path[n_node] = sum_cost
                heapq.heappush(q, (sum_cost, n_node))

    return path[1:]

result = []
for i in range(1, n+1):
    result.append(dijkstra(i, graph))

for li in result:
    li = map(lambda x: 0 if x == float('inf') else x, li)
    print(*li)

Result

  • 결과: 성공! 🎉
  • 다익스트라 알고리즘을 n번 반복하여 모든 쌍의 최단 경로를 계산하는 방법으로 문제를 해결할 수 있었다.

마무리 🤔

문제 이름이 플로이드인데 플로이드 워셜 알고리즘으로 풀면 더 빠르게 풀 수 있을것 같다. 플로이드 워셜 알고리즘에 대해 공부해봐야겠다.

  • 다익스트라의 시간 복잡도는 O(E log V)이고, 이를 V번 반복하므로 총 시간 복잡도는 O(V * E log V)가 된다.
  • 플로이드-워셜 알고리즘은 O(V^3)의 시간 복잡도를 가지는데, 이 문제처럼 V(도시 수)가 100으로 작은 경우에는 플로이드-워셜이 더 간결하고 효율적인 풀이가 될 수 있다.

하나의 알고리즘으로만 문제를 풀려고 하기보다, 문제의 조건(정점 개수, 간선 개수, 가중치 등)에 따라 더 적합한 알고리즘이 무엇인지 고민하는 습관을 길러야겠다.

⁂