[백준] 11404번 플로이드

💡문제접근

• 플로이드-워셜 알고리즘 기초 문제

📌플로이드-워셜 알고리즘이란?

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘
• 플로이드-워셜 알고리즘은 단계마다 거쳐 가는 노드를 기준으로 알고리즘을 수행
• 플로이드-워셜 알고리즘의 시간복잡도는 O(N^3)이다. 이 때, N은 노드의 개수이다.
• 플로이드-워셜 알고리즘은 최단 거리 정보를 2차원 리스트에 저장한다.
• 플로이드-워셜 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다.

# 점화식에 따라 플로이드-워셜 알고리즘을 진행(핵심)
for k 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][k] + graph[k][b])

💡코드(메모리 : 31388KB, 시간 : 636ms)

import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())
# n개의 도시(n * n)
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아 그 값으로 초기화
for _ in range(m):
    # a : 시작 도시, b : 도착 도시, c : 한 번 타는데 필요한 비용
    a, b, c = map(int, input().strip().split())
    # a → b를 연결하는 노선은 하나가 아닐 수 있다.(따라서, 최솟값으로 갱신을 해줘야한다.)
    graph[a][b] = min(graph[a][b], c)

# 점화식에 따라 플로이드-워셜 알고리즘을 진행
for k 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][k] + graph[k][b])

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

💡소요시간 : 42m