문제 URL
https://www.acmicpc.net/problem/12850
접근 방식
입력으로 받는 D 값의 범위가 1부터 10억까지 가능하다.
1초의 시간 제한 내에 풀기 위해서는 시간복잡도 O(log N)으로 해결해야 한다.
우리가 최종적으로 구해야 하는 것은 주어진 경로(그래프) 내에서 D분 동안 산책하고 정보과학관으로 돌아오는 경우의 수이다. 즉, 특정 비용을 지불했을 때 0번 노드에서 0번 노드까지 갈 수 있는 경우의 수다.
여기서 인접 행렬을 통해 경로 수를 구하는 아이디어를 떠올릴 수 있다. (난 떠올리지 못 했다.)
이 문제는 모든 산책 경로가 1분만 소요되는, 즉, 가중치가 없는 그래프를 전제로 한다. 가중치가 없는 그래프에서는 인접행렬의 원소가 0 또는 1로 구성되어 간선 유무를 나타낸다.
그리고 우리는 인접행렬의 제곱을 활용해서 경로의 수를 파악할 수 있다.
문제에서 주어진 그래프를 인접행렬 M으로 만들었다고 가정하자. 인접행렬 M의 값은 다음과 같을 것이다.
- 정보과학관과 전산관은 연결되어 있다. -> M[정보과학관][전산관] = 1
- 정보과학관과 신양관은 연결되어 있지 않다. -> M[정보과학관][신양관] = 0
위와 같은 값을 갖는 이유는 인접행렬 M은 "i에서 j로 갈 수 있는지 여부"를 나타내고 있기 때문이다.
당연하게도 한 번의 이동만으로는 정보과학관에서 신양관으로 이동할 수 없음을 알 수 있다.
하지만 두 번의 이동으로는 어떨까? 가능한 것은 물론이거니와 두 가지 경로가 존재한다.
- 정보과학관 -> 전산관 -> 신양관
- 정보과학관 -> 미래관 -> 신양관
위에서 확인한 내용을 인접행렬의 거듭제곱을 통해 똑같이 확인할 수 있다.
처음으로 주어진 그래프를 인접행렬로 나타낸 것을 M이라고 했을 때, 행렬 M의 제곱 역시 i에서 j로 갈 수 있는지 여부를 나타낸다. 그렇다면 M과 M^2는 어떻게 다를까?
결론은 M^2는 (2번의 이동으로) i에서 j로 갈 수 있는 경우의 수를 나타낸다.
행렬 M을 직접 거듭제곱해보며 알아보자.
위에서 예시를 들었듯이 정보과학관(0), 전산관(1), 미래관(2), 신양관(3) 4개의 건물만 존재한다고 가정했을 때의 인접행렬 M은 다음과 같다.
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0행렬 M을 제곱한 결과는 다음과 같다.
2 1 1 2
1 3 2 1
1 2 3 1
2 1 1 2이제 이 행렬이 어떤 의미를 갖는지 알기 위해 M^2의 (0, 0) 계산 과정을 뜯어보자. M^2(0, 0)은 행렬 곱셈식에 의해 M(0, 0) * M(0, 0) + M(0, 1) * M(1, 0) + M(0, 2) * M(2, 0) + M(0, 3) * M(3, 0)의 값을 갖게 된다.
이를 하나씩 놓고 보면 다음과 같이 구성됨을 알 수 있다.
- M(0, 0) * M(0, 0) - 정보과학관 -> 정보과학관 -> 정보과학관
- M(0, 1) * M(1, 0) - 정보과학관 -> 전산관 -> 정보과학관
- M(0, 2) * M(2, 0) - 정보과학관 -> 미래관 -> 정보과학관
- M(0, 3) * M(3, 0) - 정보과학관 -> 신양관 -> 정보과학관
결과적으로 두 번의 이동을 통해 정보과학관에서 정보과학관으로 가는 경로는 전산관과 미래관을 거치는 총 2가지의 경우의 수가 있다.
즉, 인접행렬의 거듭제곱을 통해 i에서 j까지 가는 경우의 수를 구할 수 있다. 따라서 인접행렬 M의 거듭제곱을 다음과 같이 일반화할 수 있다. 인접행렬 M의 n제곱은, n번의 이동으로 i에서 j까지 가는 경우의 수를 의미한다.
이를 문제에 적용하면, 우리는 입력으로 주어진 D번의 이동을 했을 때, 정보과학관에서 정보과학관으로 가는 경우의 수를 구하면 되는 것이다. 풀이는 다음과 같을 것이다.
- 주어진 그래프를 인접행렬(M)로 나타낸다.
- 인접행렬을 D만큼 제곱한다. -> M^D
- M^D의 (0, 0) 값을 출력한다. (MOD 연산자 신경쓰기)
정답 코드(Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
/*
0. 정보과학관
1. 전산관
2. 미래관
3. 신양관
4. 한경직기념관
5. 진리관
6. 형남공학관
7. 학생회관
*/
private static final int MOD = 1_000_000_007;
static long[][] matrix = {
{0, 1, 1, 0, 0, 0, 0, 0},
{1, 0, 1, 1, 0, 0, 0, 0},
{1, 1, 0, 1, 1, 0, 0, 0},
{0, 1, 1, 0, 1, 1, 0, 0},
{0, 0, 1, 1, 0, 1, 1, 0},
{0, 0, 0, 1, 1, 0, 0, 1},
{0, 0, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 1, 0},
};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
long[][] res = doPow(n);
System.out.println(res[0][0] % MOD);
}
private static long[][] doPow(int n) {
if (n == 1) {
return matrix;
}
long[][] temp = doPow(n / 2);
temp = multiply(temp, temp);
if (n % 2 == 1) {
temp = multiply(temp, matrix);
}
return temp;
}
private static long[][] multiply(long[][] a, long[][] b) {
long[][] temp = new long[8][8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
for (int k = 0; k < 8; k++) {
temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % MOD;
}
}
}
return temp;
}
}
회고
- 가중치가 없는 그래프가 주어졌을 때, 인접행렬을 활용하여 경로 수를 얻을 수 있다는 것을 알게 됐다. 사실 이를 잊지 않기 위해 기록한 것이기도 하다.
- 우리 학교 동아리에서 출제된 문제였다. 문제를 보자마자 아는 내용이어서 반가웠다.
