인접행렬의 제곱

1. 인접 행렬의 제곱?

그래프 관련 문제를 풀 때, 그래프를 표현하는 방법은 인접 행렬과 인접리스트가 있다. 하지만 인접 행렬은 \(O(V^2)\)의 공간복잡도를 가지기 때문에 \(O(V+E)\)의 공간복잡도를 가지는 인접리스트를 많이 쓴다.

이전에 BOJ 1533 길의 개수를 풀 때 알게된 사실인데, 가중치가 없는 인접 행렬을 \(N\)제곱하면 어떤 \(U−>V\)를 \(N\)번만에 가는 경우의 수로 계산될 수 있다는 사실을 알게 되었다.

 

어떤 \(A, B, C\)인 정점이 주어지고, 연결관계를 나타낸 인접행렬로 이 사실을 한번 알아보자.

$$\begin{pmatrix} A->A & A->B & A->C \\ B->A & B->B & B->C \\ C->A & C->B & C->C\end{pmatrix}$$

이 행렬을 제곱을 할 것인데, 첫번째 행열 원소만 관찰 해보자, 한번 제곱을 하게되면 \((A−>A−>A)+(A−>B−>A)+(A−>C−>A)\)가 된다. 이것은 길이가 \(2\)인 \(A−>A\)의 경우의 수와 같다. 한번 더 제곱을 해보자.

$$(A−>A−>A−>A)+(A−>A−>B−>A)+(A−>A−>C−>A)+(A−>B−>A−>A)+(A−>B−>B−>A)+$$

$$(A−>B−>C−>A)+(A−>C−>A−>A)+(A−>C−>B−>A)+(A−>C−>C−>A)$$

이런식으로 된다. 이것 또한 \(A−>A\)로 가는 길이가 \(3\)인 경로와 같다.

만약 엄청 큰 \(T\)라는 길이의 경우의 수를 셀때도 분할정복으로 제곱을 해주면 되므로 \(O(logT)\)만에 계산해줄 수 있다.

2. 가중치가 있는 경우

위의 사실은 가중치가 없는 그래프에서 적용되는 사실이다. 그렇다면 가중치가 있는 그래프에서는 사용하지 못하는 것일까?

가중치가 있는 그래프를 가중치가 없는 그래프로 만들어보자. 생각보다 간단한 아이디어인데, 각 정점의 가중치 만큼 새로운 정점을 만들고, 잘 연결 해주면 된다.

이런 식으로 가중치가 생각보다 작다면 효율적이게 경우의 수를 구할 수 있다.

3. 더 빠른 방법

여기까지는 수준이 안되서 이 글에서는 다루지는 않겠지만, 더 효율적인 방법도 있다.

이 방법의 시간복잡도는 \(O(V^3logT)\)인데, 여기서 키타마사법이라는 알고리즘을 적용하면 \(O(V^2logT)\)까지 줄일 수 있고,

고속 푸리에 변환까지 사용하면 \(O(VlogVlogT)\)라는 시간복잡도에 구할수도 있다고 한다. 나중에 시간이 있으면 공부해볼 가치가 있다.