[알고리즘] 행렬의 제곱 (백준 2099, The game of death)(feat. 인접행렬, 인접리스트)

들어가며

오늘 백준 문제를 풀다 시간 초과로 인해 결국 서치를 해봤는데, 행렬의 제곱을 이용해서 풀러야한다는 것을 알고 충격을 받았습니다... 역시 알고리즘,, 아직 배울 것이 너무 많이 남았습니다. 아무튼 새로운 영역을 배우게 되어 저 같은 사람들에게 조금이나마 도움이 되고자 글을 적습니다.

우선은 행렬이란?!(인접 리스트와 비교하여)

알고리즘에서 그래프를 표현하는 방법에는 두 가지가 있습니다.

1. 인접 행렬

2. 인접 리스트

 

인접 행렬

그 중 인접 행렬에 대해 우선 알아보겠습니다.

아래는 그래프를 행렬로 표현한 것입니다. 행렬에서 (A, B) 가 1이면, A에서 B로 가는 간선이 있다. 0이면, 없다는 의미가 됩니다.

또한 행렬의 모든 수를 더하면, 해당 그래프의 모든 간선의 수가 됩니다.

위의 그래프는 방향이 있는 유향 그래프인데요. 방향이 없는 무향 그래프는 아래와 같이 표현할 수 있습니다.

무향 그래프를 행렬로 표현한 인접 행렬의 특징으로는 대각선(A,A) (B,B) (C, C)를 기준으로 대칭이 되며, 행렬의 모든 수를 더해서 2로 나누면 그래프의 모든 간선의 수가 됩니다.

 

인접 행렬의 장단점

이와 같이 인접 행렬을 이용해서 그래프를 표현하면 구현이 쉽고, 특정 두 노드 사이의 간선이 있는지를 파악할 때 속도가 빠릅니다.O(1).

반면, 한 노드에 연결된 모든 노드를 찾을 때는 O(N)으로 오랜 시간이 소요됩니다. 예를 들어, 노드가 만 개가 있고, 한 노드에 연결된 노드는 한 개밖에 없을 때, 이 하나를 찾기위해 최악의 경우 만 번 파악을 해야합니다.

 

인접 리스트

다음으로는 행렬 리스트로도 그래프를 표현할 수 있습니다. 아래 그림을 보시면 이해가 바로될 것입니다.

인접 리스트의 장단점

우선 인접 행렬의 장점으로는 한 노드에 연결된 모든 노드를 찾을 때 속도가 빠르다는 것입니다. 연결된 노드의 수를 E라고 할 때 O(E)로 모든 노드의 수가 N이라고 한다면 (E < N)일 것입니다. 또한 메모리를 효율적으로 사용할 수 있습니다. 인접 행렬과 달리 연결된 노드만 사용하면 되기 때문입니다.

반면 단점으로는, 특정 두 노드의 연결 여부를 파악할 때 O(N)이 소요됩니다.

 

행렬의 제곱의 의미

결론부터 말씀드리면, 행렬를 k번 제곱했을 때, 행렬의 (N, M)의 의미는 N에서 k개의 간선을 거처 M으로 가는 방법의 수가 됩니다. 아래 그림으로 보시죠.

 

위의 행렬은 원래의 행렬을 거듭제곱한 것입니다. 이때 AA 값은 위의 수식과 같습니다.

ABBA는 A에서 B로 가는 간선 * B에서 A로 가는 간선입니다. 이 값이 1이라는 건 A에서 B를 거처 A로 돌아가는 방법이 있다는 것입니다.

같은 원리로 위의 행렬의 (N, M)의 의미는 N에서 시작해서 두 간선을 거쳐 M으로 가는 방법의 수를 의미합니다. 

 

이때 행렬을 한번 더 곱해보면, 즉 세제곱을 해보면 AA의 값은

A에서 출발해서 2개의 간선을 거친 후 A에 도착한 경우의 수 *  AA + A에서 출발해서 2개의 간선을 거친 후 B로 도착하는 경우의 수 * BA + A에서 2개의 간선을 거친 후 C에 도착하는 경우의 수 * CA

즉, A에서 출발하여 3개의 간선을 거친 후 A에 도달하는 모든 경우의 수가 됩니다.

 

그리고 마찬 가지로 행렬을 k번 제곱한다면 (N, M)의 의미는 N에서 시작해 k개의 간선을 거쳐 M으로 가는 방법이 될 것입니다.

 

빠르게 거듭제곱하기

행렬의 곱셈은 O(N^3)이 소요됩니다. k번 제곱한다면 O(k * N^3)이 소요될 것입니다.

그래서 분할 정복을 이용하여, O(logK * N^3)로 시간을 단축할 수 있습니다.

 

방법은 단순합니다.

 

1) k가 짝수인 경우

A^k = A(k/2) * A(k/2)

2) k가 홀수인 경우

A^k = A^((k-1)/2) * A^((k-1)/2)

 

나가며,

알고리즘,, 수학도 잘해야한다,,!! 그래도 새로운 것을 배워서 즐거운 기회였습니다!