플로이드·워셜의 메모리 줄이기 — N³칸에서 N²칸으로

모든 쌍 최단 거리에서 점화식을 세웠다. 답은 나오지만 $N^3$칸을 들고 있다. $N$이 1000이면 10억 칸이다. 정말 다 필요한가.

---

2층이면 충분하다

$D^k[i][j]$는 $i$에서 $j$로 가되 중간에 거치는 노드를 1번부터 $k$번까지로 제한했을 때의 최단 거리다. 위첨자 $k$가 그 제한을 가리키므로, $k$를 하나 올릴 때마다 층이 한 장 쌓인다고 보면 된다.

점화식은 $D^k[i][j] = \min(D^{k-1}[i][j],\ D^{k-1}[i][k] + D^{k-1}[k][j])$였다. 오른쪽에 나오는 층은 셋 다 $k-1$이다.

$k$층을 채우는 동안 읽는 것은 $k-1$층뿐이고, $D^{k-2}$ 이하는 한 칸도 읽히지 않는다. 다음 단계인 $k+1$층을 채울 때 읽는 것도 $k$층뿐이다.

한 층을 다 채우고 나면 그 아래 층은 두 번 다시 쓰이지 않는다.

층을 두 장만 잡고 $k$의 홀짝에 따라 번갈아 쓰면 된다. 홀수 $k$에서는 0번 장을 읽어 1번 장에 쓰고, 짝수 $k$에서는 반대로 한다.

이 글의 코드는 본편 의사코드에서 INF 검사만 덜어냈다. 한쪽이라도 INF면 덧셈을 건너뛴다는 규칙은 층을 줄여도 그대로 필요하고, 층을 어떻게 잡느냐와는 무관하다. 여기서 볼 것은 층 인덱스뿐이라 그 검사는 접어 둔다.

int D[2][n + 1][n + 1];

void floydWarshall(int W[][n + 1], int n) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            D[0][i][j] = W[i][j];

    for (int k = 1; k <= n; k++) {
        int prev = (k - 1) % 2, curr = k % 2;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                D[curr][i][j] = min(D[prev][i][j],
                                    D[prev][i][k] + D[prev][k][j]);
    }
}

마지막 반복까지 마치면 답 $D^N$은 D[n % 2]에 들어 있다.

배열이 잡는 칸을 세어 보면 한 층에 $N^2$개씩 두 층, 곧 $2N^2$개다. $O(\cdot)$ 표기는 상수배를 세지 않으므로 공간은 $O(N^3)$에서 $O(N^2)$로 내려간다. 시간은 세 겹 반복 그대로라 $O(N^3)$이다.

---

한 층으로 줄이면 무엇이 위험한가

층을 하나 더 덜어낼 수 있을까. 층 구분을 아예 없애면 코드는 이렇게 짧아진다.

int D[n + 1][n + 1];

void floydWarshall(int W[][n + 1], int n) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            D[i][j] = W[i][j];

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
}

위험은 분명하다. $D[i][k]$를 읽을 때 그것이 아직 $D^{k-1}[i][k]$인지 이미 $D^k[i][k]$로 덮인 것인지 알 수 없다. 같은 $k$ 반복 안에서 $(i,k)$ 칸이 먼저 갱신될 수 있기 때문이다.

$j$ 루프가 $k$를 지나는 순간이 그 자리다. $j = k$에서 $D[i][k]$에 $k$층 값이 쓰이고, 같은 $i$의 그 뒤 $j$들은 덮인 값을 읽는다.

$D[k][j]$도 $i$ 루프가 $k$를 지나면 같은 일을 겪는다.

점화식이 요구한 것은 $k-1$층인데 코드가 읽는 것은 뒤섞인 두 층이다.

칸을 하나씩 짚어 본다. 안쪽 문장이 읽는 칸은 $D[i][j]$, $D[i][k]$, $D[k][j]$ 셋이다.

이 중 $D[i][j]$는 걱정할 것이 없다. 하나의 $k$ 반복에서 $(i,j)$ 칸에 값을 쓰는 곳은 $i$와 $j$가 그 값을 가리키는 그 한 번뿐이고, 읽기는 그 쓰기와 같은 문장에서 먼저 일어난다. 읽는 시점의 $D[i][j]$는 아직 아무도 건드리지 않은 $D^{k-1}[i][j]$다.

위험이 남는 자리는 $D[i][k]$와 $D[k][j]$ 두 칸이다. 두 칸이 $k$ 단계에서 어떻게 변하는지만 확인하면 된다.

덮어써도 값이 같다

두 칸이 $k$ 단계 동안 값을 바꾸지 않는다면 어느 층을 읽든 결과가 같으니, 그것만 보이면 끝난다. 근거는 두 갈래로 댄다. 하나는 정의를 그대로 따지는 길이고, 하나는 점화식에 $j=k$와 $i=k$를 대입해 확인하는 길이다.

결론. 한 층짜리 코드가 읽는 위험한 자리는 $D[i][k]$와 $D[k][j]$ 두 칸이었다. 정리 1은 그 두 칸이 $k$ 단계 내내 값을 바꾸지 않는다고 말한다. 읽는 값이 어느 층이든 같으므로 덮어쓰기는 답을 바꾸지 않는다. 한 층이면 된다.

층을 오가는 인덱스도 함께 사라진다. 공간은 $O(N^2)$이고, 남는 것은 세 겹 for와 min 하나다.

---

그런데 왜 이걸 쓰는가

비교 대상을 분명히 해 둔다. 모든 노드가 서로 이어질 만큼 간선이 많은 밀집 그래프, 곧 간선 수 $M$이 대략 $N^2$개인 경우다.

이 자리에서 다익스트라는 구현이 둘로 갈린다.

우선순위 큐를 이진 힙으로 두면 한 번이 $O(M\log N)$이다. $M$ 자리에 $N^2$을 넣으면 $O(N^2\log N)$이고, $N$번 돌리면 $O(N^3\log N)$이다.

다익스트라 2에서 짚었듯 밀집 그래프에서는 힙을 걷어내고 배열을 그대로 훑어 최솟값을 찾는 쪽이 낫다. 그러면 한 번이 $O(N^2)$이고, $N$번이면 $O(N^3)$이다.

플로이드·워셜도 $O(N^3)$이다. 힙 구현을 상대로는 $\log N$ 하나를 앞서지만, 밀집 그래프에서 실제로 골라야 할 배열 구현을 상대로는 표기가 같다. 표기는 둘을 갈라 주지 못한다.

갈림은 표기에 드러나지 않는 자리, 곧 상수와 메모리 접근 패턴에 있다.

다익스트라는 어느 구현이든 시작점마다 거리 배열과 방문 표시를 새로 세우고, 반복마다 아직 확정하지 않은 노드 중 최솟값을 골라야 한다. 힙을 쓰면 큐 연산 하나하나가 $O(\log N)$번의 비교와 원소 교환을 부르고, 힙을 오르내리며 짚는 자리는 배열 위에서 절반씩 건너뛰므로 접근이 흩어진다.

플로이드·워셜에는 그런 자료구조도, 시작점마다 다시 세우는 준비도 없다. 배열 세 겹 반복만 돌고, 안쪽 $j$ 루프가 훑는 $D[i][j]$와 $D[k][j]$는 각각 한 줄을 순서대로 지나가므로 메모리 접근이 규칙적이다.

같은 $O(N^3)$ 안에서 어느 쪽이 실제로 빠른지는 그래프와 구현과 기계에 따라 달라진다. 여기서는 표기가 비긴다는 것과, 갈림이 표기 바깥에 있다는 것까지만 말해 둔다.

---