[백준] 문제 11404번 플로이드

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

 

알고리즘 설명

플로이드-워셜 알고리즘

 

개요

• 플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘으로 동적 프로그래밍 접근법을 사용합니다.
• 시간 복잡도: O(V^3), 여기서 V는 정점의 개수
• 그래프에 음수 가중치가 있을 수 있지만 음수 사이클은 허용되지 않습니다.

핵심 아이디어

• 주어진 그래프에서 정점 쌍 i,j 간의 최단 경로를 계산하며, 중간 정점 k를 포함하는 경로를 고려합니다.
• 점화식 : d[i][j] = min(d[i][j], d[i][k] + d[k][j])
  • d[i][j] : 정점 i에서 j까지의 최단거리
  • k : 중간 정점의 인덱스

최단 경로의 구조

• 최단 경로가 k를 중간 정점으로 포함하지 않는 경우
  • 경로 i → j에서 정점 k를 사용하지 않아도 최단 경로가 될 수 있습니다.
  • 이 경우, i → j의 최단 경로는 중간 정점이 k-1 이하인 경로와 동일합니다.
    • 즉, 지금까지 계산된 경로(정점 1,2, ... k-1 까지만 사용한 결과)가 그대로 최단 경로가 됩니다.
• 최단 경로가 k를 포함하는 경우
  • i → k : k로 가는 최단 경로
  • k → j : k에서 j로 가는 최단 경로
  • 이 경우 전체 경로의 길이는 d[i][k] + d[k][j]

점화식

• d[i][j] = min(d[i][j], d[i][k] + d[k][j])

알고리즘 구현

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]

    # 그래프 초기화
    for i in range(n):
        for j in range(n):
            dist[i][j] = graph[i][j]
    
    # 점화식 적용
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

 

Transitive Closure

Transitive Closure

플로이드-워셜 알고리즘은 최단 경로를 계산하는 알고리즘이지만, Transitive Closure를 계산하는 데도 활용할 수 있습니다.

• 가중치 대신 논리적 연결성(0 또는 1)으로 그래프를 표현하고, 이를 경로 갱신에 사용합니다.
• 점화식은 다음과 같이 정의됩니다:

T[i][j] = T[i][j] ∨ (T[i][k] ∧ T[k][j])

• T[i][j]: i에서 j로의 경로가 존재하는지 여부 (1 또는 0)
• T[i][k]와 T[k][j]: i에서 k로, k에서 j로의 경로가 존재하는지 여부

 

Transitive-closure algorithm

 

문제풀이

import sys

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

n = int(input())
m = int(input())

# 초기화
dist = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신으로 가는 거리는 0으로 초기화 한다.
for i in range(1, n+1) :
    dist[i][i] = 0

# 간선 정보를 입력
for _ in range(m) :
    a, b, c = map(int, input().split())
    # 동일 경로의 최소 비용만 계산
    dist[a][b] = min(dist[a][b], c)

# !플로이드-워셜 알고리즘!
for k in range(1, n+1) : # 중간에 거치는 노드
    for i in range(1, n+1) : # 시작 노드
        for j in range(1, n+1) : # 끝 노드
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# 결과 출력
for i in range(1, n+1) :
    for j in range(1, n+1) :
        if dist[i][j] == INF :
            print(0, end= ' ')
        else :
            print(dist[i][j], end= ' ')
    print()