[BOJ 1533] 길의 개수

[문제]

 

www.acmicpc.net/problem/1533

 

1533번: 길의 개수

 

[난이도]

 

- Platinum 4 (solved.ac 20.11.28 기준)

 

 

[필요 개념]

 

- 그래프

- 분할 정복을 이용한 거듭제곱

 

 

[풀이]

 

가중치가 없는 그래프인 경우, 0 또는 1로 이루어진 그래프의 인접 행렬이 주어질 때 

i에서 N번 이동해서 j로 가는 경우의 수는 인접행렬의 N제곱의 (i, j) 값이다. 

 

이를 이용하기 위해서 가중치가 주어지는 이 문제의 그래프를 조금 변형시킨다.

가중치가 5이하이기 때문에 각 정점을 5개로 나누어준다. 

예를 들어서 i번 정점이라고 한다면, i , i-1 , i-2 , i-3 , i-4 로 나누어서, 각 정점 사이를 1분 만에 이동할 수 있도록 해주는 것이다. 

따라서 j에서 i로 가는데 3분이 필요하다면 j와 i-2를 연결시켜준다. 

그러면 j에서 1초후에는 i-2로 이동하고, 2초 후에는 i-1, 3초 후에는 i에 도착할 수 있게 된다. 

 

이를 구현하기 위해서 각 정점의 번호를 5*i , 5*i - 1 , 5*i - 2 , 5*i - 3 , 5*i - 4 로 나타내고, 그래프를 만들어준다.

 

시간 복잡도는 $O({(5N)}^3 logT)$ 이다. 

 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
using ll = long long;
const int MOD = 1000003;
ll N, S, E, T;
using mat = vector<vector<ll>>;
mat A;
mat ans;
mat operator *(mat &a, mat&b) {
	mat res(5 * N + 1, vector<ll>(5 * N + 1));
	for (int i = 1; i <= 5 * N; i++) {
		for (int j = 1; j <= 5 * N; j++) {
			for (int k = 1; k <= 5 * N; k++) {
				res[i][j] += (a[i][k] * b[k][j]);
				res[i][j] %= MOD;
			}
		}
	}
	return res;
}
void mpow(void) {
	while (T) {
		if (T % 2) {
			ans = ans *A;
		}
		T /= 2;
		A = A*A;
	}
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> S >> E >> T;
	A.assign(5 * N + 1, vector<ll>(5*N+1));
	ans.assign(5 * N + 1, vector<ll>(5 * N + 1));
	for (int i = 1; i <= N; i++) {
		string s; cin >> s;
		for (int j = 0; j < sz(s); j++) {
			if (s[j]-'0' >= 1) {
				A[i * 5][(j + 1) * 5 - (s[j] - '0' - 1)] = 1;
			}
		}
		for (int j = 1; j <= 4; j++) {
			A[(i - 1) * 5 + j][(i - 1) * 5 + j + 1] = 1;
		}
	}
	for (int i = 1; i <= 5 * N; i++) ans[i][i] = 1;
	mpow();
	cout << ans[5 * S][5 * E];
}