백준 14289번 - 본대 산책 3

https://www.acmicpc.net/problem/14289

14289번: 본대 산책 3

 

결국 정보대에서 정보대까지 d번만에 가는 경우의 수를 구해야 하는 문제였다. 

 

이를 일반화해보면 "A 노드에서 B 노드까지 d번만에 가는 경우의 수"를 구해야 한다.

 

이 부분에 dp 스럽게 생각해보면 "A노드에서 B와 연결된 모든 노드까지 d-1번 만에 도착하는 경우의 수들의 합"과 같다.

 

즉 식으로 나타내면 다음과 같다.

 

dp [i][j][k] = i 노드에서 j 노드까지 k번 만에 도착하는 경우의 수라고 가정해보자.

 

그렇다면 dp[i][j][k]는 아래와 같이 구할 수 있다.

 

for(int a = 1; a <= n; i++) dp [i][j][k] += dp [i][a][k-1]*dp [a][j][1]; 

-> i 노드에서 a 노드까지 k-1번 만에 가는 경우의 수 * a 노드에서 j 노드를 갈 수 있는지(0 or 1)

 

(이해를 돕기 위해 설명해보면 k번 만에 도착하려면 k-1번 때에는 반드시 도착 노드 j와 연결되어있는 다른 노드에 있어야 한다. 이를 단순하게 점화식으로 표현한 것이다.)

 

여기까지는 충분히 떠올릴 수 있었을 것이다.

 

문제는 이제부터이다.

 

k의 제한은 결국 d의 제한과 같기 때문에 1,000,000,000, 즉 10억의 제한이 걸려있다.

이뜻은 O(k)로는 해결하지 못한다는 의미였다.

 

이 부분에서 대부분(일단 나 포함ㅎ) 막혔을 것이다.

 

그럼 어떻게 해결해야 할까?

여기서 행렬의 거듭제곱이 사용된다.

 

눈치챈 천재들도 있겠지만

for(int a = 1; a <= n; i++) dp [i][j][k] += dp [i][a][k-1]*dp [a][j][1]

위 식을 행렬로 표현해보면 다음과 같다.

 

i = 1, j = 2, k = 2, n = 4라 가정해보자.

 

가정대로 위의 for문을 실행해보면 다음과 같다

둘 다 k=1이기 때문에 결국 같은 행렬에서 연산을 진행하는데 색깔별로 곱해져서 더해진다.

 

이 부분에서 행렬의 곱셈을 사용하는 걸 확인할 수 있다. (다른 항들도 마찬가지이다. 궁금하면 직접 해보길)

 

결국 k = 2 일 때의 dp 테이블은 k=1일 때의 dp 테이블을 제곱한 테이블이 되고

k = 3 일 때는 k = 2일 때의 dp 테이블 * k = 1일 때의 dp 테이블이므로 k=1일 때의 dp 테이블의 세제곱이 된다.

 

따라서 결론적으로 k = d일 때의 dp 테이블을 k = 1일 때의 dp테이블의 d제곱을 한 테이블이다.

 

여기서 dp 테이블은 그럼 어떻게 구하는가?

 

바로 노드끼리의 간선을 나타낸 인접 행렬이 k = 1 일 때의 dp 테이블이 된다.

 

우리가 구해야 했던 건 정보대에서 정보대로 k번 만에 도착하는 경우의 수이고 정보대는 1번 노드라고 문제에서 알려줬기 때문에 

 

결론적으로 우리는 "인접 행렬을 d 제곱한 행렬의 [1][1]의 값"을 구하면 된다.

 

행렬의 거듭제곱은 분할 정복 기법을 사용하여 log 시간 안에 구할 수 있기 때문에 시간 복잡도도 만족한다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll arr[51][51] = {};
ll rem[51][51] = {}; // 고정
ll temp[51][51] = {};
ll n, m, a, b, d;

void squared(ll a[][51], ll b[][51]) {
	memset(temp, 0, sizeof(temp));
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < n; j++) {
			for (ll k = 0; k < n; k++) {
				temp[i][j] += a[i][k] * b[k][j];
				temp[i][j] %= 1000000007;
			}
		}
	}
	memcpy(arr, temp, sizeof(arr));
}

void reculs(ll x) {
	if (x == 1) return;
	if (x % 2 == 1) {
		reculs(x / 2);
		squared(arr, arr);
		squared(arr, rem);
	}
	else {
		reculs(x / 2);
		squared(arr, arr);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		a--; b--;
		arr[a][b] = 1; arr[b][a] = 1;
		rem[a][b] = 1; rem[b][a] = 1;
	}
	cin >> d; 
	reculs(d);
	cout << arr[0][0] << "\n";
}