잇창명 개발 블로그

플로이드-워셜 알고리즘의 잃어버린 항

• 댓글 달기 문제해결 알고리즘 추상대수학

이 글에는 백준 15089번/16388번 "Is-A? Has-A? Who Knowz-A?"의 풀이 스포일러가 포함되어 있습니다.

2022년 4월 중후반쯤에 백준 16388번 "Is-A? Has-A? Who Knowz-A?"라는 문제를 찾아서 푼 적이 있습니다. 3달 뒤에는 15089번이 완전히 같은 문제인 것을 확인하고 16388번 코드를 복사해서 제출했습니다. 현재는 16388번이 레이팅을 주지 않는 것으로 처리되어 있습니다.

문제 옮겨적기 (번역문)

한국어 블로그이기 때문에 독자의 편의를 위해 문제 본문을 번역합니다. 원문은 백준 링크에서 확인해 주세요.

문제

Is-a와 has-a 관계는 객체지향 프로그래밍에서 친숙한 두 가지 개념이다. 두 클래스 A와 B에 대해, A가 B의 서브클래스이면 A is-a B, A의 필드 중 하나가 타입 B를 가지면 A has-a B라고 한다. 예를 들어, 가상의 객체지향 언어(ICPC++라고 하자)에 그림 E.1과 같은 코드를 작성했다고 하면 클래스 Day는 is-a Time이고, 클래스 Appointment는 동시에 is-a DateBook이자 is-a Reminder이며, 클래스 Appointment는 has-a Day이다.

class Day extends Time        class Appointment extends Datebook, Reminder
{                             {
    ...                           private Day date;
}                                 ...
                              }

그림 E.1: ICPC++의 클래스 정의 2개.

이 두 관계는 추이적이다. 예를 들어 A is-a B이고 B is-a C이면 A is-a C임을 알 수 있다. 이는 앞의 문장에서 is-a를 모두 has-a로 바꾸어도 성립한다. Is-a와 has-a의 조합도 비슷한 성질을 띤다. 위의 예제 코드에서는 Appointment has-a Day이고 Day is-a Time이므로 Appointment has-a Time이 성립한다. 이와 비슷하게, 만약 클래스 DateBook이 has-a Year라면 Appointment is-a DateBook이므로 Appointment has-a Year도 성립한다.

이 문제에서는 여러 is-a 및 has-a 관계가 주어지고 A is/has-a B 꼴의 질의가 여러 개 주어진다. 각 질의가 참인지 거짓인지 판정하는 코드를 작성하시오.

입력

첫째 줄에 두 정수 n과 m(1 ≤ n, m ≤ 10,000)이 주어지며, n은 주어지는 is-a 및 has-a 관계의 개수, m은 질의의 개수이다. 다음 n줄에 걸쳐 c1 r c2의 꼴로 한 줄에 하나씩 관계가 주어지며, c1과 c2는 한 단어의 클래스 이름, r은 문자열 "is-a" 혹은 "has-a"이다. 그 다음에는 한 줄에 하나씩 m개의 질의가 같은 꼴로 주어진다. 위의 n + m줄에 주어지는 클래스 이름은 최대 500종류이며, 마지막 m줄에 주어지는 모든 클래스 이름은 처음 n줄에 최소한 한 번 주어진다. 주어진 모든 클래스 사이의 is-a 및 has-a 관계는 주어진 n개의 관계로부터 추론할 수 있다. Is-a 관계는 "x is-a x"인 자명한 경우를 제외하면 순환 참조를 이루지 않는다.

출력

각 질의에 대해 1부터 시작하는 질의 번호 다음에 그 질의가 참인지 거짓인지를 출력한다.

예제 입력 1

5 5
Day is-a Time
Appointment is-a Datebook
Appointment is-a Reminder
Appointment has-a Day
Datebook has-a Year
Day is-a Time
Time is-a Day
Appointment has-a Time
Appointment has-a Year
Day is-a Day

예제 출력 1

Query 1: true
Query 2: false
Query 3: true
Query 4: true
Query 5: true

최단거리가 왜 거기서 나와

문제를 잘 읽어보면 is-a와 has-a가 다음 성질을 가짐을 알 수 있습니다. 모든 클래스 A, B, C에 대해...

이 문제에 is-a만 나왔다면 최단 경로 알고리즘(특히 플로이드-워셜 알고리즘)을 아주 조금만 응용해서 풀 수 있었겠지만 하필 has-a가 is-a와 상호작용을 하기 때문에 이렇게 풀기는 어렵습니다. 최단 경로 알고리즘 대신 무슨 방법으로 풀 수 있을지 알고리즘 분류를 살펴봅시다.

아무래도 플로이드-워셜 알고리즘이 정해가 맞는 것 같습니다. 그런데 구체적으로 플로이드-워셜 알고리즘을 어떻게 이용한다는 걸까요?

저는 문제를 처음 풀 당시에 이 방법을 엄밀한 증명 없이 사용했습니다.

이 방법에는 세 가지 꺼림칙한 점이 있습니다.

그럼에도 불구하고 저는 이 코드를 그대로 제출했고 맞았습니다!!를 받았습니다. 그 뒤로 7달 동안 이 문제를 잊고 살다가 갑자기 다시 생각났고, 이번에는 혼자서 생각하다가 막혀서 컴퓨터과학 스택 익스체인지의 도움을 받기로 합니다.

대수적 경로 문제

알고 보니 실수가 아닌 가중치로 최단 경로를 구하는 문제에는 이미 algebraic path problem이라는 이름이 붙어 있었습니다. 이 글에서는 "대수적 경로 문제"라고 번역하겠습니다.

위에 링크한 질문의 답변을 보면 아무 가중치로나 최단 경로를 구할 수는 없고, 특정한 조건, 구체적으로는 덧셈이 멱등이고 클레이니 스타가 정의된 반환 구조를 이루어야 한다고 합니다. 갑자기 낮선 단어를 막 쓰는데 하나씩 짚어보면 단순한 조건들로 이루어져 있고 그 조건들 하나하나가 이유 없이 있는 것이 아니니 너무 겁먹지 않으셔도 됩니다.

대수적 구조 '반환'

"덧셈이 멱등이고 클레이니 스타가 정의된 반환"이 구체적으로 무슨 뜻인지 알아봅시다.

우선 반환에 대한 설명부터 해보자면, 대표적인 반환 중 하나로는 음이 아닌 정수의 덧셈과 곱셈을 들 수 있습니다. 자연수끼리 덧셈과 곱셈을 할 때 교환법칙, 결합법칙, 분배법칙이 성립하고 항등원이 있는 것은2 학교에서 배우기 때문에(저는 그렇게 기억하고 있습니다) 증명하는 것이 그렇게 어렵지는 않을 것 같습니다. 최단 거리 알고리즘에서는 \(\infty\)로 초기화를 하는 경우도 흔하기 때문에 음이 아닌 정수에 \(\infty\)를 추가할 수 있고, \(\infty + x = \infty\), \(\infty \times 0 = 0 \times \infty = 0\), 0이 아닌 \(x\)에 대해 \(\infty \times x = x \times \infty = \infty\)로 정의하면 이렇게 정의한 확장 자연수도 반환을 이룹니다. 그런데 이 정의를 보고 나면 자연스러운 의문이 들 것 같습니다.

"최단" 경로를 구한다면서 \(\min\)은 어디 갔나요? 대소 비교는 어떻게 해요?

열대 반환

사실 \(\oplus\)가 덧셈이고 \(\otimes\)가 곱셈이라는 고정관념을 버리면 확장 자연수에 대해 이 조건을 만족하는 연산자 쌍을 하나 더 찾을 수 있습니다. 바로 \(a \oplus b = \min(a, b)\), \(a \otimes b = a + b\)입니다.

이것도 나무랄 데 없는 반환이네요. 덧셈과 곱셈 대신 최솟값과 덧셈 연산이 있는 이 반환에는 열대 반환(tropical semiring)이라는 이름이 붙어 있습니다.3

\(\min\) 연산과 대소 비교의 관계

대소 비교도 \(\min\)으로부터 도출할 수 있는데, 그 과정을 설명하려면 잠깐 삼천포로 빠져야 합니다.

1줄 요약: \(a \le b\)를 \(\min(a, b) = a\)로 정의하면 됩니다.

대수적 구조 '반격자'

반격자(semilattice)는 덧셈과 곱셈 대신 대소 비교를 일반화한 대수적 구조인데4, 서로 다른 두 가지 정의가 있습니다.

순서론적 정의

백준 7568번 "덩치" 문제를 풀어본 적이 있나요? 이 문제에서는 몸무게와 키의 순서쌍으로 덩치를 나타내는데, \((56, 177) > (45, 165)\)처럼 대소 비교가 되는 쌍도 있지만 \((45, 181)\)과 \((55, 173)\)처럼 그렇지 않은 쌍도 있습니다. 이렇게 순서의 개념은 있지만 비교가 가능하지 않은 쌍도 허용하는 것을 부분 순서라고 합니다. 엄밀하게는 다음 성질을 만족하는 이항 관계를 부분 순서라고 합니다.

부분 순서가 있는 어떤 집합에 다음 성질을 가지는 연산 \(\wedge\)를 정의할 수 있으면 그 집합과 연산을 통틀어 반격자라고 합니다.

추상대수학적 정의

어떤 집합에 다음 성질을 만족하는 연산 \(\wedge\)를 정의할 수 있으면 그 집합과 연산을 통틀어 반격자라고 합니다.

한 정의에서 다른 정의로

겉보기에는 두 정의가 전혀 달라 보이지만, 사실 두 정의는 동치입니다. 즉, 한 정의에서 다른 정의를 도출할 수 있습니다.

둘 중 이 글에서는 추상대수학적 정의에서 순서론적 정의로 넘어가는 것에 관심이 있습니다. \(a \le b\)를 \(a \wedge b = a\)로 정의하면 \(\wedge\) 연산의 세 성질이 각각 \(\le\)의 성질 하나씩으로 바뀝니다.

이렇게 추상대수학적으로 올바르게 정의한 \(\wedge\)가 있으면 항상 올바른 부분 순서 \(\le\)를 얻을 수 있습니다. 연산자를 정의했는데 대소 비교가 따라온 것입니다.

\(\min\)이 위의 세 성질을 만족함은 이미 위에서 보였으니, \(\le\) 연산자도 자연스럽게 사용할 수 있습니다. \(\min\) 연산이 어디 간 게 아니라 \(\oplus\)에 줄곧 숨어 있었던 것입니다.

삼천포의 삼천포

반격자가 왜 "반"격자인지 설명을 안 하고 넘어가면 찜찜하실 분이 있을 것 같아서 언급하는 건데, 똑같은 부분 순서로 하한 연산 \(\wedge\)뿐만 아니라 상한 연산 \(\vee\)도 정의할 수 있으면 그걸 격자(lattice)라고 합니다.

대수적 성질에서 경로 연산으로

기존 플로이드-워셜 알고리즘의 두 연산 중 \(\min\)이 \(\oplus\)라면, 나머지 \(+\)은 자연스럽게 \(\otimes\)에 대응시킬 수 있습니다. 이 점을 염두에 두고 두 연산의 성질이 대수적 경로 문제와 어떻게 관련이 있는지 정리하면 이렇습니다.

이제 대수적 경로 문제와 "거리"의 개념을 엄밀하게 정의할 수 있습니다.

그런데 사실 이 정의에는 문제가 있습니다. 두 정점 사이에 사이클이 있는 경로가 있으면 그 사이클의 거리 \(w\)에 대해 \(1 \oplus w \oplus (w \otimes w) \oplus (w \otimes w \otimes w) \oplus \cdots\)의 무한합을 구해야 합니다. 저희 아직 무한합을 엄밀하게 정의 안 하지 않았나요?

클레이니 스타로 무한합 다루기

사실 "특정한 조건" 중에 빠진 것이 하나 있습니다. 다시 읽어볼까요?

특정한 조건, 구체적으로는 덧셈이 멱등이고 클레이니 스타가 정의된 반환 구조를 이루어야 한다고 합니다.

클레이니 스타 \(w^*\)가 바로 위에서 엄밀하게 정의 안 하고 넘어갔던 무한합 \(1 \oplus w \oplus (w \otimes w) \oplus (w \otimes w \otimes w) \oplus \cdots\)입니다. 즉, 클레이니 스타는 사이클의 최단 거리를 일반화합니다.

클레이니 스타가 항상 정의되는 것은 아닙니다. 예를 들어 아까 보았던 열대 반환에서 임의의 \(x\)에 대해 \(x^* = \min(0, x, x + x, x + x + x, \cdots) = 0\)이지만, 이를 음의 정수까지(\(-\infty\)를 빼고) 확장하면 음의 정수 \(-x\)에 대해 \((-x)^* = \min(0, -x, -x - x, -x - x - x, \cdots)\)는 정의되지 않습니다. 즉, 클레이니 스타가 정의되지 않는 경우는 음의 사이클을 일반화합니다.

사실 정수나 실수로 최단 거리를 구할 때는 굳이 사이클이 있는 경로를 확인하지 않는데, 이는 사이클의 거리 \(x\)가 음이 아니면 \(x^* = \min(0, x, x + x, x + x + x, \cdots) = 0\)이 그 사이클을 아예 지나가지 않는 것보다 나을 바가 없고, 음이면 최단 경로를 구하는 것이 의미가 없기 때문입니다. 일반적으로 \(\otimes\)의 항등원 \(1\)과 \(x^*\)가 정의되는 모든 \(x\)에 대해 \(1 \le x^*\)이면 사이클 계산을 생략하는 기존 알고리즘을 써도 문제 없이 잘 돌아갑니다. 역으로, 이 식이 성립하지 않으면 기존의 알고리즘을 사용할 수 없고 더 일반적인 알고리즘을 고안해서 써야 합니다.

객체지향 가중치도 최단 경로를 구할 수 있을까?

이제 제가 제일 궁금해하던 질문에 답해 보겠습니다. 플로이드-워셜 알고리즘에 객체지향 가중치를 넣어도 잘 돌아갈까요?

이 질문에 "예"라고 답할 조건은 다음과 같습니다.

이거 말고도 또 있습니다.

solved.ac 디스코드 서버의 포스트 "15089, 16388 Is-A? Has-A? Who Knows-A? - 난이도 및 태그 논의" 스크린샷

저는 결국 플로이드-워셜이 정해가 아니라는 충격적인 진실을 마주하고야 말았습니다. 사실 문제 제한이 작아서 DFS로도 충분히 풀린다는 걸 지금까지 간과하긴 했는데 이번 글에서는 대수적 경로 문제 얘기만 하기로 했으니 무시하겠습니다.

WFGJ 알고리즘

그렇다고 문제를 아예 못 푸는 건 아니고, 아까 언급했듯이 더 일반적인 알고리즘을 고안해서 쓰면 됩니다. 다행히 S. Rajopadhye의 논문 The Algebraic Path Problem에서 저자가 "WFGJ 알고리즘"이라고 명명한 알고리즘의 설명을 읽어볼 수 있습니다. 이 논문은 Günter Rote의 A Systolic Array Algorithm for the Algebraic Path Problem (Shortest Paths; Matrix Inversion)을 요약한 것이고, WFGJ 알고리즘이라는 이름은 Warshall의 추이 폐포 알고리즘, Floyd의 최단 거리 알고리즘(플로이드-워셜 알고리즘), Gauss-Jordan의 역행렬 알고리즘이 모두 이 알고리즘의 특수한 경우라는 의미로 첫 글자를 딴 것입니다.

플로이드-워셜 알고리즘 돌아보기

WFGJ 알고리즘을 이해하려면 플로이드-워셜 알고리즘을 어떻게 유도했는지를 먼저 이해해야 합니다. 우선 몇 가지 개념과 표기를 정의하겠습니다. 정점에는 1번부터 \(n\)번까지 번호가 붙어 있습니다.

알고리즘 설명에 필요한 성질을 미리 적어 두겠습니다. 증명은 생략합니다.

이때 \(P(i, j, k)\)에 속하는 경로는 다음의 두 가지 경우로 나눌 수 있습니다.

즉, \(P(i, j, k)\)는 위의 두 경우의 합집합 \(P(i, j, k - 1) \cup P(i, k, k - 1) \otimes P(k, j, k - 1)\)이고 \(f\)의 성질을 이용해 최솟값의 점화식 \(F(i, j, k) = F(i, j, k - 1) \oplus F(i, k, k - 1) \otimes F(k, j, k - 1)\)으로 바꿀 수 있습니다. 이 점화식을 그대로 계산하는 대신 배열 업데이트로 바꾸면 오늘날 사용하는 플로이드-워셜 알고리즘이 됩니다. 여기서부터는 설명의 편의를 위해 \(F(\cdots)\) 없이 \(P(\cdots)\)만 사용하겠습니다.

여기서 "최단 경로에는 사이클이 없다"는 가정을 버리고 알고리즘을 다시 유도해 봅시다.

새로운 알고리즘 만나기

\(P(i, j, k)\)에 속하는 경로는 다음의 두 가지 경우로 나눌 수 있습니다.

위의 논문에서는 다음과 같은 방법으로 분해했습니다.

이때의 의사코드는 다음과 같습니다. 함수 star가 정의되어 있고 0, 1, +, *이 적당히 오버로딩이 되어 있음을 가정합니다.

dist = [[0] * n] * n
for (from, to, len) in edge:
	dist[from][to] += len

for k in [0, n):
	new_dist = [[0] * n] * n
	
	# i = j = k
	for i in [0, n):
		new_dist[i][i] = star(dist[i][i])
	
	# i != k, j = k
	for i in [0, n):
		if i != k:
			new_dist[i][k] = dist[i][k] * new_dist[k][k]
	
	# j != k
	for i in [0, n):
		for j in [0, n):
			if j != k:
				new_dist[i][j] = new_dist[i][k] * dist[k][j]

쓰기 편하게 최적화하기

여기부터는 제가 독자 연구한 내용으로, 잘못된 정보가 포함되어 있을 수 있습니다. 건조한 증명이 몇 문단 동안 이어지므로 이 부분은 읽지 않고 넘어가셔도 됩니다.

여기까지만 유도해도 올바른 알고리즘은 나오지만, 이대로 놔두면 실 사용이 정말 불편한 알고리즘이 됩니다. 원래 플로이드-워셜 알고리즘만큼 편하게 쓸 수 있게 개선했으면 좋겠네요.

하나의 점화식으로 통일하기

위의 논문에서 제시한 방법 대신 모든 \(i\), \(j\), \(k\)의 조합에서 처음으로 나오는 \(k\)번 정점과 마지막으로 나오는 \(k\)번 간선을 기준으로 두 번 분할하면 \(i\)번 정점에서 \(k\)번 정점으로 가는 머리, \(k\)번 정점의 사이클로 이루어진 몸통, \(k\)번 정점에서 \(j\)번 정점으로 가는 꼬리로 나눌 수 있습니다. 단, \(i = k\)이면 머리가, \(j = k\)이면 꼬리가 자명한 경로가 되어 없어집니다.

\[P(i, j, k) = P(i, j, k - 1) \cup P(i, k, k - 1) \otimes P(k, k, k) \otimes P(k, j, k - 1)\]

이때 \(P(k, k, k) = P(k, k, k - 1)^*\)이므로 다음과 같이 바꿀 수 있습니다.

\[P(i, j, k) = P(i, j, k - 1) \cup P(i, k, k - 1) \otimes P(k, k, k - 1)^* \otimes P(k, j, k - 1)\]

이제 점화식이 한 가지 모양으로 고정됐을 뿐만 아니라 \(P(\cdots, \cdots, k - 1)\)에만 의존하는 식이 되었습니다. 점화식에 \(P(\cdots, \cdots, k)\) 항이 포함되었다면 동적 계획법을 사용할 때 순서를 생각하면서 루프를 돌려야 했을 것입니다.

하나의 2차원 배열로 바꾸기

하지만 아직 2차원 배열을 2개 만들고 루프를 돌 때마다 배열을 저글링하는 불편한 점이 있습니다. 플로이드-워셜 알고리즘처럼 배열 하나에 업데이트만 해도 올바르게 동작할까요?

알고리즘을 이렇게 고칠 수 있으려면 동적 계획법을 돌릴 때 원래보다 경로를 "조금 많이 잡아도" 잘 돌아간다는 것을 증명해야 합니다. 구체적으로는 최적화된 알고리즘의 2차원 배열을 \(P'(i, j)\)라 할 때(값이 계속 바뀌기 때문에 \(k\)를 따로 적지 않는 것에 유의해 주세요), \(k\)번째 루프가 돌아가기 전에 \(P(i, j, k - 1) \subset P'(i, j) \subset P(i, j, n)\)이었으면 \(k\)번째 루프가 돌고 나서는 \(P(i, j, k) \subset P'(i, j) \subset P(i, j, n)\)을 만족하는 것을 보이고 싶습니다. 이렇게 하면 루프가 \(n\)번 돈 뒤에는 \(P(i, j, n) \subset P'(i, j) \subset P(i, j, n)\)이므로 \(P'(i, j) = P(i, j, n)\)이 됩니다.

우선 첫 번째 루프가 돌기 전에는 \(P(i, j, 0) \subset P'(i, j) \subset P(i, j, n)\)을 만족해야 합니다. 이는 \(P'(i, j) \leftarrow P(i, j, 0)\)으로 초기화해서 쉽게 만족할 수 있습니다.

\(k\)번째 루프가 돌 때는 원래의 점화식을 변형해서 \(P'(i, j) \leftarrow P'(i, j) \cup P'(i, k) \otimes P'(k, k)^* \otimes P'(k, j)\) 꼴의 대입을 하는데, 이 시점에서 \(P'(i, j)\)의 값은 루프를 \(k - 1\)번 혹은 \(k\)번 돈 결과이므로 둘 중 하나를 만족합니다.

그런데 원래 점화식에 의해 \(P(i, j, k - 1) \subset P(i, j, k)\)이므로 \(P(i, j, k - 1) \subset P'(i, j) \subset P(i, j, n)\)이 성립합니다. 이는 우변의 다른 값에도 똑같이 적용됩니다.

여기에 아까 언급한 여러 가지 포함 관계 성질과 \(P(a, b, n) \otimes P(b, c, n) = P(a, c, n)\)임을 이용하면(\(P(i, j, n)\)은 정의상 \(i\)번 정점에서 \(j\)번 정점으로 가는 모든 경로의 집합이므로) 목표로 했던 \(P(i, j, k) \subset P'(i, j) \cup P'(i, k) \otimes P'(k, k)^* \otimes P'(k, j) \subset P(i, j, n)\)을 얻을 수 있습니다.

글을 처음 쓰기 시작했을 때는 예상하지 못했었는데 WFGJ 알고리즘도 "그냥" 루프 3개에 배열 1개로 돌릴 수 있네요!

진정 하나의 점화식으로 통일하기

사실 위의 문단에서는 "\(i = k\)이면 머리가, \(j = k\)이면 꼬리가 자명한 경로가 되어 없어"진다고 해 놓고 바로 밑의 점화식에는 그 사실을 반영하지 않았습니다. 실제로 글을 쓰면서 제가 최적화를 잘 하고 있는지 계속 제출을 해보고 있는데 이 이유로 틀렸습니다를 받았습니다.

문제가 생긴 이유를 한 마디로 정리하자면 \(P(i, i, 0)\)에 "자명한 경로"를 포함하지 않았기 때문입니다. 이 문제는 3중 루프를 돌리기 전에 \(P'(i, i)\)에 그 "자명한 경로"를 직접 추가해서 해결할 수 있습니다. 실제 코드에서는 dist[i][i] += 1과 같은 모양이 되겠습니다. 이렇게 하고 나면 완성된 점화식은 숨은 조건 없이 이렇게 한 줄이 됩니다.

\[P'(i, j) = P'(i, j) \cup P'(i, k) \otimes P'(k, k)^* \otimes P'(k, j)\]

단, \(i = k\)이거나 \(j = k\)이면 \(P'(i, k)\)나 \(P'(k, j)\)가 "자명한 경로"만 있는 집합이어야 하는데 그렇지 않게 되는 문제가 있습니다. 어차피 이 알고리즘은 경로를 "조금 많이 잡아도" 잘 돌아가니 넘어가겠습니다.

결론: 플로이드-워셜 알고리즘의 잃어버린 항

위의 최적화를 모두 적용하고 난 의사코드는 다음과 같습니다.

dist = [[0] * n] * n
for (from, to, len) in edge:
	dist[from][to] += len
for i in [0, n):
	dist[i][i] += 1

for k in [0, n):
	for i in [0, n):
		for j in [0, n):
			dist[i][j] += dist[i][k] * star(dist[k][k]) * dist[k][j]

참고로 (대수적 버전의) 플로이드-워셜 알고리즘의 의사코드는 다음과 같습니다.

dist = [[0] * n] * n
for (from, to, len) in edge:
	dist[from][to] += len
for i in [0, n):
	dist[i][i] += 1

for k in [0, n):
	for i in [0, n):
		for j in [0, n):
			dist[i][j] += dist[i][k] * dist[k][j]

두 알고리즘은 말 그대로 한 항 차이입니다. 이 글의 제목에서 언급했던 "잃어버린 항"이 바로 이것을 말하는 것입니다.

이쯤 되면 좀 우려먹는 것 같긴 하지만 정규 표현식 가중치도 위에서 언급한 적당한 반환 구조를 이루고, 여기에 WFGJ 알고리즘을 적용하면 갑자기 ε-NFA를 정규 표현식으로 바꾸는 알고리즘을 공짜로 얻을 수 있습니다. 이외에도 이 구조를 이루는 가중치는 얼마든지 생각할 수 있으니 이 한 항이 얼마나 중요한 역할을 하는지 느껴볼 수 있습니다. 다만 이 알고리즘은 모든 쌍의 최단 경로를 구하기 때문에(\(O(n^3)\)) 그럴 필요가 없을 떄는 시간 낭비가 있을 수 있고, 웬만한 최단 경로 문제는 모두 실수 선에서 해결할 수 있어 활용 기회가 좀처럼 없었던 것이 아쉬운데 앞으로는 이런 문제를 더 자주 만나볼 수 있었으면 좋겠습니다.

  1. 이 글에서 다루는 이 대수적 구조에서 클레이니 스타의 정의를 이 문단의 마지막 네 가지 성질로 바꾼 것을 클레이니 대수라고 합니다. ↩

  2. 대한민국의 교육 과정에서는 0이 자연수가 아니지만, 논의의 일관성과 편의를 위해 0을 자연수로 취급하는 경우도 자주 있습니다. 이 글에서도 여기서부터 "자연수"를 "음이 아닌 정수"의 의미로 사용하겠습니다. ↩

  3. "열대"라는 이름은 이 분야의 연구자인 헝가리계 브라질 컴퓨터과학자 Imre Simon이 열대 지역에 살았기 때문에 붙여졌다는 것 같습니다. 왜 멀쩡한 사람 이름 대신 기후 이름을 붙였는지는 잘 모르겠습니다. ↩

  4. 구체적으로 반격자에는 상한(join) 반격자와 하한(meet) 반격자가 있는데, 어차피 둘 다 방향만 빼고 같은 개념이니 여기서는 하한 반격자를 "반격자"라고 하겠습니다. ↩

플로이드-워셜 알고리즘의 잃어버린 항