인접행렬 거듭제곱

인접행렬과 인접리스트

  $V$개의 정점이 있고 $E$개의 간선(방향이든 무방향이든 상관없지만, 여기서는 편의를 위해 무방향이라 가정하자)이 있는 그래프 $G(V,\, E)$를 생각하자. 이러한 그래프를 저장하는 방법은 크게 두 가지가 있다.

 

  첫 번째는 인접행렬(Adjacency Matrix)이다. 어떤 두 점이 인접한지, 즉 두 점 사이에 간선이 있는지를 표시하는 행렬로 그래프를 표현한다. 실제 프로그래밍에서는 아래 코드와 같이 $V \times V$ 크기의 배열 g를 사용해서 g[A][B] 값을 A번 정점과 B번 정점 사이 간선의 개수로 저장한다.

#include <stdio.h>
#define NMAX 1000

int g[NMAX][NMAX];

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);

	while (M--) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a][b]++, g[b][a]++; // a와 b 사이 간선이 여러 개인 상황도 커버 가능하다. 
	}

	// ...
}

  이렇게 하면, 임의의 두 정점 사이에 간선이 존재하는지를 $\mathcal O(1)$에 판단할 수 있다. 하지만 인접행렬의 경우, 요구하는 공간 복잡도가 $\mathcal O(V^2)$이고, 모든 정점에 연결된 모든 간선을 순회하는 데에도 총 $\mathcal O(V^2)$ 만큼의 시간이 걸리기 때문에 $V$가 $10^4$을 넘어가 버리면 메모리 제한과 시간 제한에 걸려 사용하기가 힘들어진다.

 

  인접행렬의 이러한 점을 보완하기 위해 등장한 표현 형식이 바로 두 번째 방법, 인접리스트(Adjacency List)다. 인접리스트는 각 정점마다 해당 정점과 인접한 정점들을 저장한다. 실제 구현은, $V$개의 동적 배열(보통은 STL의 std::vector를 이용한다)을 만들어 g[A]에 A번 정점과 인접한 정점들을 추가하는 방식으로 구현한다.

#include <cstdio>
#include <vector>
#define NMAX 100000

std::vector<int> g[NMAX];

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);

	while (M--) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}

	// ...
}

  이 경우 공간 복잡도 및 모든 간선 순회 시의 시간 복잡도는 모두 $\mathcal O(V+E)$가 된다. 사실 $V$개의 정점이 있는 그래프에서는 (간선 중복을 허용하지 않을 경우) 최대 $\frac{V(V-1)}{2}$개의 간선이 있을 수 있어서 $\mathcal O(V+E)$와 $\mathcal O(V^2)$이 차이가 없을 수도 있으나, 실제 문제에선 입력량 크기 제한 등의 현실적인 이유로 $V$가 클 경우 $E$가 $V^2$에 비해 현격히 작은─일명 희소한(sparse)─그래프가 주어지는 게 대부분이다($V = 10^5,\, E = 2 \times 10^5$ 등). 그렇기에 실제 연산량이나 메모리 사용량 면에서 상당한 향상이 생기게 된다. 다만 어떤 두 정점 사이에 간선이 있는지 확인할 때 최악의 경우 $\mathcal O(E)$만큼의 시간이 걸릴 수도 있다는 게 단점이다.

 

인접행렬 거듭제곱

  이렇게만 보면 인접행렬이 왜 있는 거지? 싶겠지만… 사실 인접행렬도 그 나름대로의 쓸모가 있다. 한 번 이러한 문제를 생각해 보자: 그래프 $G(V,\, E)$가 있고, 두 정점 $a$, $b$와 양의 정수 $K$가 주어질 때, $a$, $b$를 잇는 경로 중 길이가 정확히 $K$인 경로의 개수는 몇 개인가?

 

  가장 쉽게 떠오르는 생각은, 백트래킹으로 일일이 모든 경우를 다 확인해 보는 방식이지만, 이는 굉장히 느릴 게 뻔하다. 조금 더 머리를 굴려 보면, 일단 DP를 사용할 수 있겠다는 생각을 할 수 있다.

 

$dp[i][j] :=$ $a$번 정점에서 $i$개의 간선을 거쳐 $j$번 정점에 도달하는 경우의 수

 

로 놓으면,

$$dp[i][j] = \displaystyle \sum_{p\ \in\ g[j]} dp[i-1][p]$$

라는 식을 세울 수 있다($g[i]$는 $i$와 인접한 정점들의 집합). $i$개의 간선을 거쳐 $j$번 정점에 도달하려면, $i-1$개의 간선을 거친 후에는 $j$와 인접한 정점에 있어야 하기 때문이다. 따라서 이 식을 이용해, $dp[K][b]$를 $\mathcal O(KE)$에 구할 수 있고, 그것이 곧 우리가 구하고자 하는 답이다.

 

  혹은 인접행렬을 이용해서 이렇게도 식을 세울 수 있다: $dp[k][x][y] :=$ $x$번 정점에서 $k$개의 간선을 거쳐 $y$번 정점에 도달하는 경우의 수라 하면

$$dp[k][x][y] = \sum_{i=1}^V dp[k-1][x][i] \times g[i][y]\quad \cdots\ (\star)$$

라고 할 수 있다(여기서 $g$는 $G$의 인접행렬이다). $x$번 정점에서 $y$번 정점으로 $k$번만에 가는 것은, $k-1$번째에 $i$번 정점을 들른 뒤 $i$번 정점에서 $y$번 정점으로 가는 것과 같고, 이때 $i$는 $1$부터 $V$까지 가능하기 때문이다. 이 경우 답은 $dp[K][a][b]$가 되고, 이를 구하는 데 걸리는 시간 복잡도는 $\mathcal O(KV^2)$이 된다.

  이렇게 주어진 문제를 두 가지의 DP 형태로 해결할 수 있는데, 사실 잘 생각해 보면 두 DP 식은 근본적으로 동일하다. 단지 인접리스트 관점으로 보느냐, 아니면 인접행렬 관점으로 보느냐의 차이일 뿐이다.

 

  허나 $K$가 아주 큰 경우(예를 들어 10억 정도)라면? 시간 복잡도를 보면 알겠지만, 이 경우에는 DP 방법도 무용지물이다. 우리는 이대로 문제를 포기해야만 하는 걸까? 그렇지 않다!

  $(\star)$ 식을 다시 보자. $k=1$일 경우, $dp[1]$ 배열값은 정의에 의해 인접행렬 그 자체가 된다. 따라서 $k=2$일 경우 $(\star)$ 식은

$$dp[2][x][y] = \sum_{i=1}^V g[x][i] \times g[i][y]$$

가 된다. 어라? 우변의 식, 어디선가 많이 본 형태 같은데…? 라고 생각했다면 제대로 본 것이다. 그렇다. 우변의 식은 행렬의 곱셈에서 나오는 식과 정확히 일치한다! 정확히는, '곱셈 결과의 $x$행 $y$열에 해당하는 값'과 같다. 따라서 $k=2$일 때 $dp[2]$ 배열은 $g \times g = g^2$과 같다! $k=3$일 경우에는? 이전 결과를 대입하면, 마찬가지로 행렬 곱셈 꼴이 되어 $g^2 \times g = g^3$과 같게 된다. 이제 대충 어떤 규칙성이 있는지 다들 눈치챘을 것이다.

 

  이쯤에서 이 글의 제목과도 관련 있는 명제를 이야기하고자 한다. 결론적으로, 인접행렬을 $k$ 제곱한 행렬이 곧 $dp[k]$가 된다! 이에 대한 증명은 수학적 귀납법을 이용하여 쉽게 할 수 있으나, 위의 논의를 거의 그대로 되풀이하는 것에 지나지 않으므로 생략한다. 여튼 행렬의 거듭제곱은 로그 시간에 할 수 있고, $N \times N$짜리 행렬끼리의 곱셈 연산은 $\mathcal O(N^3)$에 할 수 있으므로 우리는 본 문제를 $\mathcal O(V^3 \log K)$의 시간 복잡도로 해결할 수 있다.

 

  이러한 기법을 흔히 인접행렬 거듭제곱이라 부르며, 이를 이용해서 풀 수 있는 문제들이 꽤 존재한다. (문제는 난이도 순으로 나열하려고 노력하였다.)

 

• CodeUp 3480. 외식의 빗자루 ─ 이 글에서 소개한 문제와 동일하다. 단, 이 문제는 $K$가 작기 때문에 위에서 소개한 DP 방식으로도 풀리며, 심지어 DP 풀이가 인접행렬 거듭제곱보다 더 빠르다.
• BOJ 12850. 본대 산책 2 ─ 그래프 모양이 정해져 있으니 그걸 그대로 인접행렬로 옮겨주면 된다.
• BOJ 14289. 본대 산책 3 ─ 역시 이 글에서 소개한 문제와 같다. $D$분 뒤에 원래 위치로 돌아오는 가짓수를 세면 된다. (근데 이 문제가 solved.ac상으로는 12850번보다 난이도가 낮다.(...))
• BOJ 12916. K-Path ─ 이 글에서 소개한 문제를 모든 정점 쌍에 적용한 문제다. 이는 단순히 행렬의 모든 성분을 다 더해 주면 된다.
• BOJ 17401. 일하는 세포 ─ 살짝 변형된 문제다. 인접행렬이 매 초마다 바뀌므로, 인접행렬을 거듭제곱하는 게 아니라 $0$초부터 $D$초까지의 인접행렬을 곱하면 된다. 단, 이를 $D$번의 곱셈으로 해결하면 당연히 시간초과가 되고, 인접행렬이 $T$초 주기로 순환하는 것을 이용해서 연산 횟수를 줄여야 하는 문제다.
• BOJ 1533. 길의 개수 ─ 이 글에서 소개한 문제와 유사하나, 간선의 길이가 5 이하라는 조건이 있다. 어렵게 생각하지 말고, 길이가 2 이상인 간선에 정점을 추가해서 길이 1짜리 간선 여러 개로 나누는 아이디어를 떠올려 보자. 하지만 모든 간선에 대해 이런 방식으로 정점을 추가하게 되면 정점의 개수가 너무 많아져서 제한 시간 내에 문제를 해결할 수 없다. 그 대신 한 정점당 4개의 정점만을 추가로 만들고, 추가된 정점들을 원래 간선 길이에 맞게 단방향 간선들로 적절히 연결해 주면, $5N$개의 정점만으로 문제를 해결할 수 있다.

 

인접행렬 거듭제곱 구현의 예시를 들기 위해, 내가 BOJ 12916. K-Path 문제에 제출했던 코드를 첨부한다.

#include <cstdio>

const int P = 1e9 + 7;

struct Mat {
    int N, a[101][101];

    Mat(int n, int t = 0): N(n) {
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j) a[i][j] = i == j ? t : 0;
    }

    Mat operator* (const Mat &r) {
        Mat ret(N);
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                for (int k = 0; k < N; ++k) ret.a[i][j] = (ret.a[i][j] + a[i][k] * r.a[k][j]) % P;
        return ret;
    }
};

int main()
{
    int N, K, i, j;
    scanf("%d", &N);

    Mat G(N);
    for (i = 0; i < N; ++i)
        for (j = 0; j < N; ++j) scanf("%d", &G.a[i][j]);

    Mat A(N, 1);
    while (K) {
        if (K & 1) A = A * G;
        G = G * G; K >>= 1;
    }

    int ans = 0;
    for (i = 0; i < N; ++i)
        for (j = 0; j < N; ++j) ans = (ans + A[i][j]) % P;

    printf("%d", ans);
    return 0;
}

 

더 나아가기

  여기서 한 가지 의문이 들 수도 있다. 그렇다면 $K$에 이어 $V$가 더 큰 경우에는 어떻게 할 것인가? 확실히 $\mathcal O(V^3 \log K)$라는 시간 복잡도는 $V$가 그다지 크지 않을 경우에만 사용할 수 있다. $V$가 300 정도만 되어도 1초 내에 통과하기 어렵다. 실제로 위에서 소개한 문제들 모두 $V$가 충분히 작은 문제들뿐이었다. 그런데 $V$가 크다면? 이번에야말로 항복 선언을 할 때일까? …라고 생각할 수 있지만, 이 시간 복잡도 또한 개선이 가능하다!

 

  아주 간략하게 개요만 설명하면 다음과 같다. 다시 $(\star)$ 식으로 돌아가 보면, 이 식은 길이 $V$짜리 선형 점화식의 형태다. 따라서 키타마사 법을 이용해서 시간 복잡도를 단축할 수 있으며, 그때의 시간 복잡도는 $\mathcal O(V^2 \log K)$가 되고, 여기에 고속 푸리에 변환까지 동원하면 최종적으로 $\mathcal O(V \log V \log K)$라는 경이로운 시간 복잡도를 도출할 수 있다. 하지만 이 글에서 이에 대한 세부적인 내용까지 설명하는 것은 이 글의 원래 목적에서 많이 벗어나는 것이기도 하고, 무엇보다 나 또한 아직은 잘 모르는 영역이기 때문에 이 내용들은 본 글에서 다루지 않을 것이다. 그래서 이 이상의 내용에 관심이 있는 분들은, 링크를 들어가서 읽어 보고 스스로 탐구하거나 여기보다 더 좋은 타 블로그를 참고하기를 권한다.

 

  여튼 요점은 시간 복잡도를 줄일 수는 있지만, 그에 반비례하여 코드의 복잡도(?)가 올라간다는 것 정도만 알고 있으면 된다. 인접행렬 거듭제곱만으로도 충분히 풀리는 문제가 대다수이기에 고급 알고리즘을 모른다고 걱정할 필요가 없으며, 만에 하나 이렇게까지 해야 하는 문제가 나온다면, 어차피 그때부터는 템플릿 싸움(...)이기 때문에 본인이 코드를 짤 수 있느냐 없느냐는 그다지 큰 문제가 아닐 것이다…….