[BOJ] 1389

less than 1 minute read

케빈 베이컨의 6단계 법칙

1389번 https://www.acmicpc.net/problem/1389

플로이드-워셜(Floyd Warshall) 알고리즘을 사용하는 문제입니다.
(모든 정점에서 모든 정점으로의 거리를 구하고 싶을 때 사용합니다.)
k번째 노드를 추가했을 때 i로부터 j까지의 최단거리를 최단i, j(k)이라고 하면,
최단i, j(k) = min(최단i, j(k - 1), 최단i, k(k - 1) + 최단k, j(k - 1))
임을 이용하면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1389.cpp

Categories:

Updated:

Leave a comment