Warshall과 도달 가능성의 논리

A에서 B로 갈 수 있고 B에서 C로 갈 수 있다면, A에서 C로도 갈 수 있습니다. 당연해 보이는 이 사실을 그래프 전체에 적용하면 "어느 정점에서 어느 정점으로 갈 수 있는가"를 모든 정점 쌍에 대해 한꺼번에 구할 수 있습니다. 작업 사이의 선후 관계에서 어떤 작업이 다른 작업에 간접적으로라도 의존하는지 알아야 할 때처럼, 쌍마다 갈 수 있는지만 알면 되는 문제가 있습니다. 깊이 우선 탐색을 정점마다 한 번씩 해도 되지만, 이 글에서는 표 하나를 세 겹의 반복문으로 채우는 Warshall 알고리즘을 다룹니다. 이 알고리즘의 구조는 다음 글에서 모든 쌍의 최단 거리를 구하는 데 그대로 다시 쓰입니다.

도달 가능성을 표로 나타내기

정점 i에서 간선을 하나 이상 따라가 정점 j에 닿을 수 있으면 i에서 j로 도달 가능(reachable)하다고 합니다. 모든 쌍의 도달 가능성을 참과 거짓으로 적은 표를 그래프의 추이 폐포(transitive closure)라고 부릅니다. A에서 B, B에서 C로 갈 수 있으면 A에서 C로도 갈 수 있다는 성질을 추이성이라 하는데, 직접 간선만 적힌 관계에 이 성질을 끝까지 적용해 채운 결과라는 뜻입니다. 관계에 필요한 쌍만 더해 추이성을 갖게 만드는 추이 폐포를 집합으로 정의하고, 새 쌍이 생기지 않을 때까지 반복해 구하는 방법은 이산수학의 관계의 합성과 폐포에서 다룹니다.

출발점은 인접 행렬입니다. 인접 행렬은 간선 하나로 갈 수 있는 쌍만 참이므로, 여러 간선을 거쳐야 하는 쌍을 채워 넣는 것이 할 일입니다. 정점 A, B, C와 간선 A→B, B→C가 있다면 인접 행렬에서 A→C는 거짓이지만, 추이 폐포에서는 A→B→C로 갈 수 있으므로 참이어야 합니다.

중간 정점을 하나씩 허용한다

Warshall 알고리즘은 경로가 거쳐도 되는 중간 정점을 하나씩 늘려 가며 표를 고칩니다. 처음 표는 중간 정점을 하나도 거치지 않는, 곧 간선 하나짜리 경로만 알고 있습니다. 첫 단계에서는 0번 정점을 중간에 거쳐도 되도록 허용하고, 다음 단계에서는 0번과 1번을 허용하는 식으로 k번째 단계에서 중간 정점으로 0번부터 k번까지를 허용합니다. 마지막 단계가 끝나면 모든 정점을 중간에 거칠 수 있으므로, 표에는 모든 경로가 반영됩니다.

k번 정점을 새로 허용할 때 i에서 j로 가는 경로는 두 가지뿐입니다. k를 거치지 않는 경로라면 이전 단계의 표가 이미 알고 있습니다. k를 거치는 경로라면 i에서 k까지 가는 부분과 k에서 j까지 가는 부분으로 나뉘고, 두 부분은 모두 k보다 앞선 정점만 중간에 거치므로 역시 이전 단계의 표가 알고 있습니다. 그래서 다음 갱신식이 나옵니다.

reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

or는 두 가지 경로 가운데 하나만 있어도 된다는 뜻이고, and는 k를 거치려면 i에서 k까지와 k에서 j까지가 둘 다 있어야 한다는 뜻입니다. 아래 그림은 두 부분 경로를 k에서 이어 붙이는 모습입니다. 그림의 화살표 하나는 간선 하나가 아니라, 이미 앞선 중간 정점들을 거쳤을 수도 있는 부분 경로입니다.

간선 A→B, B→C에서 A→C의 값은 단계마다 다음과 같이 바뀝니다.

코드로 옮기기

def transitive_closure(adjacency, reflexive=False):
    n = len(adjacency)
    reach = [[bool(value) for value in row] for row in adjacency]
    if reflexive:
        for i in range(n):
            reach[i][i] = True
    for k in range(n):
        for i in range(n):
            for j in range(n):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach


def show(names, table):
    print("  " + " ".join(names))
    for name, row in zip(names, table):
        print(name, " ".join("1" if value else "0" for value in row))


names = ["A", "B", "C"]
adjacency = [[0, 1, 0], [0, 0, 1], [0, 0, 0]]
show(names, transitive_closure(adjacency))
show(names, transitive_closure(adjacency, reflexive=True))

  A B C
A 0 1 1
B 0 0 1
C 0 0 0
  A B C
A 1 1 1
B 0 1 1
C 0 0 1

reach는 인접 행렬의 0과 1을 bool로 바꾼 새 표라서, 함수는 넘겨받은 인접 행렬을 바꾸지 않습니다. show는 표를 읽기 쉽게 1과 0으로 출력하며, i행 j열이 1이면 i에서 j로 갈 수 있다는 뜻입니다. 첫 표에서 A행 C열이 1이 되어 A에서 C로 갈 수 있음을 알 수 있습니다.

자기 자신으로 가는 경로를 어떻게 정할까

첫 표의 대각선, 곧 A에서 A, B에서 B, C에서 C는 모두 0입니다. 이 그래프에는 출발점으로 되돌아오는 사이클이 없어서, 간선을 하나 이상 따라가 자기 자신에게 돌아오는 길이 없기 때문입니다. 반면 "간선을 하나도 따라가지 않고 그 자리에 있는 것"도 도달로 본다면 모든 정점은 자기 자신에게 도달할 수 있습니다. reflexive=True는 이 두 번째 정의를 택해 처음부터 대각선을 참으로 두며, 두 번째 표가 그 결과입니다.

두 정의는 어느 쪽이 맞고 틀린 문제가 아니라, 풀려는 문제가 무엇을 묻느냐에 달려 있습니다. "이 작업이 자기 자신에게 순환 의존하는가"를 묻는다면 간선을 하나 이상 따라가는 첫 번째 정의가 필요하고, 그 대각선이 참인 정점은 사이클 위에 있습니다. 결과를 다른 사람에게 넘길 때는 어느 정의로 계산했는지를 함께 알려야 표를 잘못 읽지 않습니다.

반복 순서가 중요한 이유

세 겹의 반복에서 k가 가장 바깥에 있어야 합니다. 갱신식은 i에서 k까지와 k에서 j까지가 이전 단계의 표, 곧 k보다 앞선 정점만 거친 경로를 이미 완전히 반영하고 있다는 전제 위에 서 있습니다. k를 가장 안쪽으로 옮겨 i, j, k 순서로 반복하면, i와 j의 칸 하나를 채우는 시점에 필요한 다른 칸들이 아직 채워지지 않았을 수 있습니다. 간선 A→C, B→A, C→B로 이루어진 사이클에서 두 순서를 비교해 보겠습니다.

def transitive_closure(adjacency):
    n = len(adjacency)
    reach = [[bool(value) for value in row] for row in adjacency]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach


def closure_wrong_order(adjacency):
    n = len(adjacency)
    reach = [[bool(value) for value in row] for row in adjacency]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach


cycle = [[0, 0, 1], [1, 0, 0], [0, 1, 0]]
print(transitive_closure(cycle)[0])
print(closure_wrong_order(cycle)[0])

[True, True, True]
[False, True, True]

세 정점이 사이클을 이루므로 A에서 A로 돌아오는 길 A→C→B→A가 있고, 올바른 순서는 A행을 모두 참으로 채웁니다. 잘못된 순서는 가장 먼저 A→A를 계산하는데, 이때 A에서 출발해 중간을 거쳐 A로 돌아오려면 C→A 같은 칸이 참이어야 합니다. 그런데 C→A는 C→B→A의 두 간선을 거쳐야 알 수 있는 값이라 아직 채워지지 않았고, 한번 지나간 A→A 칸은 다시 계산하지 않으므로 거짓으로 남습니다.

왜 맞고 왜 끝나는가

k번 단계가 끝났을 때 reach[i][j]가 참인 것은, i에서 j로 가면서 중간 정점으로 0번부터 k번까지만 거치는 경로가 있을 때와 정확히 같습니다. 이것을 k에 대한 귀납법으로 보일 수 있습니다. 시작할 때는 중간 정점이 없는 경로, 곧 간선 하나짜리 경로만 참입니다. k번 정점까지 허용한 경로는 k를 거치지 않거나, k를 한 번 거쳐 두 부분으로 나뉩니다. 한 경로가 k를 여러 번 거친다면 처음 k에서 마지막 k까지의 사이클 부분을 잘라 내도 i에서 j로 가는 경로가 남으므로, k를 한 번만 거치는 경우만 생각하면 됩니다. 두 경우 모두 이전 단계의 표로 판정되므로 갱신식이 정확히 이 조건을 계산합니다.

마지막 단계가 끝나면 모든 정점을 중간에 거칠 수 있으므로, 표는 간선을 하나 이상 따라가는 모든 경로를 반영한 추이 폐포입니다. 반복은 정해진 횟수인 n³번이므로 반드시 끝납니다.

비용과 다른 방법과의 비교

세 겹의 반복이 n번씩 돌므로 시간은 O(n³)이고, 표 하나를 쓰므로 공간은 O(n²)입니다. 정점마다 DFS나 BFS를 한 번씩 해도 모든 쌍의 도달 가능성을 구할 수 있으며, 이때 시간은 O(V(V + E))입니다. 간선이 적은 그래프라면 이쪽이 훨씬 빠르고, 한 출발점에서의 도달 가능성만 필요하다면 DFS 한 번이면 충분합니다. Warshall 알고리즘은 간선이 많은 그래프이거나, 인접 행렬로 이미 주어진 작은 그래프에서 코드가 짧고 실수할 곳이 적다는 장점이 있습니다.

더 깊이: 행 전체를 한 번에 합치기

갱신식을 다시 보면, reach[i][k]가 참일 때만 reach[i][j]가 reach[k][j] 덕분에 참이 될 수 있습니다. 곧 i에서 k로 갈 수 있으면, k에서 갈 수 있는 모든 정점에 i에서도 갈 수 있으므로 i행에 k행을 통째로 or하면 됩니다. 행 하나를 정수 하나의 비트들로 나타내면 이 일을 정수의 | 연산 한 번으로 할 수 있습니다. 아래 코드에서 i행의 j번 비트가 1이면 i에서 j로 갈 수 있다는 뜻입니다.

def closure_bits(rows):
    reach = list(rows)
    n = len(reach)
    for k in range(n):
        for i in range(n):
            if reach[i] >> k & 1:
                reach[i] |= reach[k]
    return reach


names = ["A", "B", "C"]
rows = [0b010, 0b100, 0b000]
for name, row in zip(names, closure_bits(rows)):
    print(name, [names[j] for j in range(len(names)) if row >> j & 1])

A ['B', 'C']
B ['C']
C []

0b010은 이진수로 적은 정수이며, 1번 비트인 B만 1이라 A의 이웃이 B뿐이라는 뜻입니다. reach[i] >> k & 1은 i행의 k번 비트를 꺼내는 식이고, reach[i] |= reach[k]는 k행의 비트들을 i행에 합칩니다. 반복은 n²번으로 줄지만 | 연산 한 번이 n비트를 다루므로 전체 비용은 여전히 n³에 비례합니다. 다만 컴퓨터는 한 번에 64비트 정도를 함께 처리하므로 실제로는 훨씬 빨라집니다.

정리

• 추이 폐포는 모든 정점 쌍에 대해 간선을 따라 도달할 수 있는지를 적은 표입니다.
• Warshall 알고리즘은 중간에 거쳐도 되는 정점을 0번부터 하나씩 허용하며 reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])로 표를 고칩니다.
• k가 가장 바깥 반복이어야, 갱신에 쓰는 칸들이 앞선 중간 정점만 거친 경로를 이미 모두 반영하고 있습니다.
• 대각선을 처음부터 참으로 둘지는 간선을 하나도 따라가지 않는 경우를 도달로 볼지에 대한 정의의 문제이며, 어느 정의로 계산했는지 밝혀야 합니다.
• 시간은 O(n³), 공간은 O(n²)이며, 간선이 적은 그래프에서는 정점마다 DFS나 BFS를 하는 편이 빠를 수 있습니다.

연습 문제

1. 서로 오가는 두 정점

간선 A→B와 B→A만 있는 그래프에서, reflexive=False로 계산한 A→A는 참일까요?

2. and를 or로 바꾸면

갱신식의 and를 or로 바꾸어 reach[i][j] or (reach[i][k] or reach[k][j])로 계산하면, 간선 A→B 하나만 있는 정점 세 개의 그래프에서 어떤 잘못된 결과가 나올까요?

3. 정점마다 탐색하는 방법과 비교하기

정점이 1000개이고 간선이 3000개인 그래프에서 모든 쌍의 도달 가능성을 구할 때, Warshall 알고리즘과 정점마다 BFS를 하는 방법의 연산 규모를 비교하세요.

다음 글 Floyd–Warshall과 음수 사이클에서는 같은 반복 구조에서 or와 and를 min과 덧셈으로 바꾸어, 모든 정점 쌍 사이의 최단 거리를 구합니다.