백준 11404번 - 플로이드

플로이드 문제 바로 가기

풀이 날짜: 2026-01-09

baekjoon 알고리즘 문제 풀이

풀이 코드

import sys
input = sys.stdin.readline

INF = 10**5
n = int(input())
m = int(input())

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

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

for _ in range(m):
    a,b,c = map(int, input().split())
    if c < graph[a][b]:
        graph[a][b] = c

for i in range(1,n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][i] + graph[i][b])

for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            print(0, end=" ")
        else:
            print(graph[i][j], end=" ")
    print()
  

문제 핵심 요약:

“도시 A에서 도시 B까지 가는 최소 비용”을 모든 (A, B) 쌍에 대해 출력하는 것.

내가 선택한 풀이 방식

각 도시를 하나씩 중간 경유지로 가정하며, “직접 가는 경로”와 “경유해서 가는 경로”를 비교해 최단 거리를 갱신하는 방식을 사용했다.
초기에는 모든 도시 쌍을 ‘갈 수 없는 상태’로 만들어두었고, 자기 자신으로 가는 비용만 0으로 설정했다.
이후에는 입력으로 주어진 노선을 행렬에 반영할 때는, 같은 출발-도착 도시를 잇는 노선이 여러 개 있을 수 있기 때문에 항상 최소 비용만 저장하도록 처리했다.

마지막으로는, 각 도시를 중간 경유지로 두는 3중 반복문을 통해서 모든 도시 쌍에 대한 최단 거리를 계산했다.

구현 과정에서 겪은 어려움

플로이드-워셜 알고리즘 자체보다, 각 변수와 값이 어떤 의미를 가지는지 정확히 이해하고 코드를 구현하는 것이 어려웠다.
특지 인접 행렬을 어떻게 초기화해야 하는지에 대한 개념이 명확하지 않아서, 헷갈렸던 문제이다.

처음에는 모든 값을 0으로 초기화했는데, 이로 인해 “길이 없음”과 “비용이 0”인 상태를 구분하지 못했다.
이 상태에서는 간선 입력 과정에서 최소 비용을 비교하는 로직이 제대로 작동하지 않았고, 결과적으로 그래프 자체가 거의 갱신되지 않는 문제가 발생했다.
겉보기에는 코드가 정상적으로 돌아가는 것처럼 보였기 때문에, 어디가 잘못됐는지 파악하는 데 시간이 오래 걸렸다.

또 하나 헷갈렸던 부분은 플로이드 점화식이었다.
graph[a][b] = min(graph[a][b], graph[a][i] + graph[i][b])라는 식이 단순한 공식처럼 느껴져, 처음에는 왜 반드시 +가 들어가야 하는지 직관적으로 이해하지 못했다.
하지만 “a에서 b로 바로 가는 경우”와 “i를 경유해서 가는 경우”를 비교한다는 관점으로 다시 해석하면서, 이 식이 경유 비용의 합을 비교하는 핵심 로직이라는 것을 이해하게 되었다.

마지막으로 출력 형식도 예상보다 까다로웠다.
각 행마다 줄바꿈을 해주지 않으면 모든 결과가 한 줄로 출력되기 때문에, print(value, end=” “)와 print()의 역할 차이를 정확히 이해해야 했다.