플로이드-워셜 알고리즘

1. 개요2. 설명

2.1. 코드

1. 개요

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

시간복잡도는

O(V^3)

이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이다. 로버트 플로이드와 스티븐 워셜이 개발하였으며, 이 중 플로이드는 공로를 인정받아 튜링상을 받았다.[1][2]

2. 설명

플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다.

조금 더 구체적인 설명을 위해, 임의의 노드 s 부터 e 까지 가는데 걸리는 최단거리를 d[s][e]라고 하자. (처음에 d[s][e]의 값은 노드 s와 노드 e가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)[3]로 초기화한다.) 이 d[s][e]를 구하기 위해서, s와 e 사이의 모든 노드 m에 대해, 현재 d[s][e]에 저장되어 있는 값과, d[s][m]+d[m][e]의 값을 비교한다. 이 때 d[s][m]+d[m][e]의 값이 현재의 d[s][e] 값보다 작으면, d[s][e]를 d[s][m]+d[m][e] 의 값으로 업데이트한다.

2.1. 코드

단순히 반복문을 3번 중첩시키기만 하면 되기 때문에 큰 어려움 없이 간결하게 구현할 수 있다. 단, 유의하여야 할 점은 for문에서 가운데 노드(m)가 제일 위에 있어야 한다는 점이다.

C언어로 구현한 플로이드-워셜 알고리즘은 다음과 같다.(C++)

#!syntax cpp
void Floyd_Warshall() {
  for(m=1; m<=N; m++)
    for(s=1; s<=N; s++)
      for(e=1; e<=N; e++)
        if (d[s][e] > d[s][m] + d[m][e])
			d[s][e] = d[s][m] + d[m][e];
}

다음 프로그램은 플로이드-워셜 알고리즘을 사용하여 그래프를 인접 행렬 형태로 입력받아 임의의 노드로부터 임의의 노드까지 가는 최단거리를 구해준다.

#!syntax cpp
//Floyd calculates shortest dist from all nodes to all nodes

/*
0. Initialize d with inf except adj nodes
1. Find d[s][e] by comparing current d[s][e] with d[s][m]+d[m][e]
*/

#include <stdio.h>
#define INF 1<<20

int d[1000][1000];
int n, m;

void Init()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if(i!=j) d[i][j] = INF; 
}

void Floyd()
{
	for (int m = 1; m <= n; m++) //가운데 노드
		for (int s = 1; s <= n; s++) //시작 노드
			for (int e = 1; e <= n; e++) //마지막 노드
				if (d[s][e] > d[s][m] + d[m][e])
					d[s][e] = d[s][m] + d[m][e]; //가운데를 거쳐가는 것이 더 빠르면 그걸로 업데이트한다.
}

int main()
{
	scanf("%d %d", &n, &m); //n: 노드의 개수, m: 간선의 개수
	Init(); //d의 모든 값을 무한으로 초기화(단, d[i][i]는 0)
	for (int i = 0; i < m; i++) { //인접행렬 입력받기
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		d[x][y] = c;
	}

	Floyd();

	for (int i = 1; i <= n; i++) //모든 경로의 최단거리 출력
		for(int j=1; j<=n; j++)
			printf("Shortest dist from %d to %d: %d\n", i, j, d[i][j]);
}

파이썬 코드는 다음과 같다. (참고로 노드의 이름은 0 ~ n-1로 되어 있어야 한다.)

#!syntax python
def floyd_warshall(graph):
    """Floyd-Warshall algorithm
    
    Time Complexity = O(n^3)"""
    n = len(graph)
    
    d = [[float('Inf')] * n for _ in range(n)]
    for i in graph:
        for j, w in graph[i]:
            d[i][j] = w
        d[i][i] = 0

    for m in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][m] + d[m][j])
                
    return d

# test
graph = {0: [(1, 1), (2, 4)],  # (node, weight)
		1: [(2, 2), (3, 5)],
		2: [(3, 1)],
		3: []}

d = floyd_warshall(graph)
for row in d:
	print(row)

[1] 정확히 이야기하면, 워셜의 알고리즘을 기반으로 하여 플로이드가 아이디어를 제시한 것에 가깝다. 때문에 플로이드 알고리즘이라고도 부를 때도 있다.[2] 다만 이 업적만으로 튜링상을 받은 건 아니고, 플로이드는 컴퓨터 과학 전반적으로 기여한 바가 지대하다. 플로이드는 특히 초창기 프로그래머로서 컴파일러의 기반이 되는 파서(parser)의 선구자였고, 프로그래밍 언어 이론을 비롯해 자동화된 프로그램 검증과 합성 등 분야의 개척자였다. 소프트웨어 공학의 아버지라고 불려도 무방하다.[3] 정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다. 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편이다.

C++의 경우 std::numeric_limits::max, Python의 경우 타입에 따라 sys.maxint나 sys.float_info.max 등을 사용하면 안전한 값을 구할 수 있다. math.inf도 있다. 참고로 자주 사용되는 int의 경우 2,147,483,647이 양의 최대값으로, 이걸 16진수로 표현하게 되면 0x7FFFFFFF이다. F가 7개. 이걸로도 모자랄 것 같으면 64비트 정수 타입을 쓰거나 아예 실수 타입을 써야 한다. 또한 INF값에 더하기 등의 특정 연산을 수행할 경우 오버플로로 인해 오작동할 수 있으니 이를 고려한 INF값과 적절한 자료형을 정하는 것이 좋다. 거리가 너무 커지는 경우 문제 자체에서 특정 수로 나눈 나머지를 출력하라는 식으로 오버플로를 예방하기도 한다.

#!if version2 == null
{{{#!wiki style="border:1px solid gray;border-top:5px solid gray;padding:7px;margin-bottom:0px"
[[크리에이티브 커먼즈 라이선스|[[파일:CC-white.svg|width=22.5px]]]] 이 문서의 내용 중 전체 또는 일부는 {{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/다익스트라 알고리즘|다익스트라 알고리즘]]}}}{{{#!if external != "o"
[[다익스트라 알고리즘]]}}}}}} 문서의 {{{#!if uuid == null
'''uuid not found'''}}}{{{#!if uuid != null
[[https://namu.wiki/w/다익스트라 알고리즘?uuid=7eba7b39-6d58-4b55-8f7c-52ab6d2d2c10|r116]]}}} 판{{{#!if paragraph != null
, [[https://namu.wiki/w/다익스트라 알고리즘?uuid=7eba7b39-6d58-4b55-8f7c-52ab6d2d2c10#s-3|3번 문단]]}}}에서 가져왔습니다. [[https://namu.wiki/history/다익스트라 알고리즘?from=116|이전 역사 보러 가기]]}}}

#!if version2 != null
{{{#!wiki style="display: block;"
{{{#!wiki style="border:1px solid gray;border-top:5px solid gray;padding:7px;margin-bottom:0px"
[[크리에이티브 커먼즈 라이선스|[[파일:CC-white.svg|width=22.5px]]]] 이 문서의 내용 중 전체 또는 일부는 다른 문서에서 가져왔습니다.
{{{#!wiki style="text-align: center"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="text-align: left; padding: 0px 10px"
{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/다익스트라 알고리즘|다익스트라 알고리즘]]}}}{{{#!if external != "o"
[[다익스트라 알고리즘]]}}}}}} 문서의 {{{#!if uuid == null
'''uuid not found'''}}}{{{#!if uuid != null
[[https://namu.wiki/w/다익스트라 알고리즘?uuid=7eba7b39-6d58-4b55-8f7c-52ab6d2d2c10|r116]]}}} 판{{{#!if paragraph != null
, [[https://namu.wiki/w/다익스트라 알고리즘?uuid=7eba7b39-6d58-4b55-8f7c-52ab6d2d2c10#s-3|3번 문단]]}}} ([[https://namu.wiki/history/다익스트라 알고리즘?from=116|이전 역사]])
{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid2 == null
'''uuid2 not found'''}}}{{{#!if uuid2 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph2 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]]){{{#!if version3 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid3 == null
'''uuid3 not found'''}}}{{{#!if uuid3 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph3 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version4 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid4 == null
'''uuid4 not found'''}}}{{{#!if uuid4 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph4 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version5 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid5 == null
'''uuid5 not found'''}}}{{{#!if uuid5 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph5 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version6 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid6 == null
'''uuid6 not found'''}}}{{{#!if uuid6 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph6 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version7 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid7 == null
'''uuid7 not found'''}}}{{{#!if uuid7 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph7 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version8 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid8 == null
'''uuid8 not found'''}}}{{{#!if uuid8 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph8 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version9 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid9 == null
'''uuid9 not found'''}}}{{{#!if uuid9 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph9 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version10 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid10 == null
'''uuid10 not found'''}}}{{{#!if uuid10 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph10 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version11 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid11 == null
'''uuid11 not found'''}}}{{{#!if uuid11 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph11 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version12 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid12 == null
'''uuid12 not found'''}}}{{{#!if uuid12 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph12 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version13 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid13 == null
'''uuid13 not found'''}}}{{{#!if uuid13 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph13 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version14 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid14 == null
'''uuid14 not found'''}}}{{{#!if uuid14 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph14 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version15 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid15 == null
'''uuid15 not found'''}}}{{{#!if uuid15 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph15 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version16 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid16 == null
'''uuid16 not found'''}}}{{{#!if uuid16 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph16 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version17 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid17 == null
'''uuid17 not found'''}}}{{{#!if uuid17 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph17 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version18 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid18 == null
'''uuid18 not found'''}}}{{{#!if uuid18 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph18 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version19 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid19 == null
'''uuid19 not found'''}}}{{{#!if uuid19 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph19 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version20 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid20 == null
'''uuid20 not found'''}}}{{{#!if uuid20 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph20 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version21 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid21 == null
'''uuid21 not found'''}}}{{{#!if uuid21 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph21 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version22 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid22 == null
'''uuid22 not found'''}}}{{{#!if uuid22 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph22 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version23 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid23 == null
'''uuid23 not found'''}}}{{{#!if uuid23 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph23 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version24 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid24 == null
'''uuid24 not found'''}}}{{{#!if uuid24 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph24 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version25 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid25 == null
'''uuid25 not found'''}}}{{{#!if uuid25 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph25 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version26 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid26 == null
'''uuid26 not found'''}}}{{{#!if uuid26 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph26 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version27 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid27 == null
'''uuid27 not found'''}}}{{{#!if uuid27 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph27 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version28 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid28 == null
'''uuid28 not found'''}}}{{{#!if uuid28 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph28 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version29 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid29 == null
'''uuid29 not found'''}}}{{{#!if uuid29 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph29 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version30 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid30 == null
'''uuid30 not found'''}}}{{{#!if uuid30 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph30 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version31 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid31 == null
'''uuid31 not found'''}}}{{{#!if uuid31 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph31 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version32 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid32 == null
'''uuid32 not found'''}}}{{{#!if uuid32 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph32 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version33 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid33 == null
'''uuid33 not found'''}}}{{{#!if uuid33 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph33 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version34 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid34 == null
'''uuid34 not found'''}}}{{{#!if uuid34 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph34 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version35 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid35 == null
'''uuid35 not found'''}}}{{{#!if uuid35 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph35 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version36 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid36 == null
'''uuid36 not found'''}}}{{{#!if uuid36 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph36 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version37 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid37 == null
'''uuid37 not found'''}}}{{{#!if uuid37 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph37 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version38 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid38 == null
'''uuid38 not found'''}}}{{{#!if uuid38 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph38 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version39 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid39 == null
'''uuid39 not found'''}}}{{{#!if uuid39 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph39 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version40 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid40 == null
'''uuid40 not found'''}}}{{{#!if uuid40 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph40 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version41 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid41 == null
'''uuid41 not found'''}}}{{{#!if uuid41 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph41 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version42 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid42 == null
'''uuid42 not found'''}}}{{{#!if uuid42 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph42 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version43 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid43 == null
'''uuid43 not found'''}}}{{{#!if uuid43 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph43 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version44 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid44 == null
'''uuid44 not found'''}}}{{{#!if uuid44 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph44 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version45 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid45 == null
'''uuid45 not found'''}}}{{{#!if uuid45 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph45 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version46 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid46 == null
'''uuid46 not found'''}}}{{{#!if uuid46 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph46 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version47 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid47 == null
'''uuid47 not found'''}}}{{{#!if uuid47 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph47 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version48 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid48 == null
'''uuid48 not found'''}}}{{{#!if uuid48 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph48 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version49 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid49 == null
'''uuid49 not found'''}}}{{{#!if uuid49 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph49 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}{{{#!if version50 != null
{{{#!wiki style="display: block;"

{{{#!wiki style="display: inline-block"
{{{#!if external == "o"
[[https://namu.wiki/w/|]]}}}{{{#!if external != "o"
[[]]}}}}}} 문서의 {{{#!if uuid50 == null
'''uuid50 not found'''}}}{{{#!if uuid50 != null
[[https://namu.wiki/w/?uuid=|r]]}}} 판{{{#!if paragraph50 != null
, [[https://namu.wiki/w/?uuid=#s-|번 문단]]}}} ([[https://namu.wiki/history/?from=|이전 역사]])}}}}}}}}}}}}}}}}}}}}}

플로이드-워셜 알고리즘

1. 개요

2. 설명

2.1. 코드

분류