[BOJ] 백준 17401. 일하는 세포 (Platinum V)

클래스 문제에 있길래 풀어보았다.

문제는 아래와 같다.

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

17401번: 일하는 세포

---

의식의 흐름 및 해설

우선 D가 굉장히 크다.

어지간한 그래프 탐색 (dfs, bfs, floyd)로는 시간복잡도 내에 절대 불가능해보인다.

그런데, 이렇게 이동 경우의 수를 구하는 문제, 어디서 많이 보지 않았나?

바로 본대산책2에서 본 듯하다.

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

12850번: 본대 산책2

위와 같이 경우의수를 구할 땐, 인접행렬과 그래프 성질을 이용해주면 된다.

여기서는 주기에 따라 다른 행렬을 곱하는데, 여기서 주의해주어야한다.

 

예제2처럼 T가 3이라 해보자.

두 가지 방법이 있는데 어떤 것으로 해결하겠는가?

어차피 A^3 * B^3 * C^2 이나, (ABC)^2*AB나 똑같으니까 

A=power(A, 3) * B=power(B, 3) * C=power(C, 2) 하면 되지 않을까~? 할 수도 있다.

그러나 제일 중요한 점은, 행렬은 교환법칙이 성립하지 않는다.

 

자세한 이유는 아래 블로그의 포스팅을 참고하자.

https://mathbang.net/564

행렬의 곱셈에 대한 성질

 

따라서 2번 방법인 (ABC)^2*AB로 문제에서 주어진 순서를 지켜서 해주어야한다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 101;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const ll MOD = 1e9 + 7;
int T, N, D;
class Matrix {
public:
	vector<vector<ll>> v;
	Matrix() {
		v = vector<vector<ll>>(N, vector<ll>(N, 0));
	}
	Matrix operator*(const Matrix O) const {
		Matrix R;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < N; k++) {
					R.v[i][j] += v[i][k] * O.v[k][j];
					R.v[i][j] %= MOD;
				}
			}
		}
		return R;
	}
};
Matrix power(Matrix M, ll k) {
	Matrix R;
	if (!k) {
		for (int i = 0; i < N; i++) {
			R.v[i][i] = 1;
		}
		return R;
	}
	if (k == 1)return M;
	R = power(M, k / 2);
	R = R * R;
	if (k % 2)
		R = R * M;
	return R;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> T >> N >> D;
	Matrix M[MAX];
	for (int i = 0; i < N; i++) {
		M[0].v[i][i] = 1;
	}
	for (int i = 1; i <= T; i++) {
		int t;
		cin >> t;
		while (t--) {
			ll a, b, cost;
			cin >> a >> b >> cost;
			a--; b--;
			M[i].v[a][b] = cost;
		}
	}
	for (int i = 1; i <= T; i++) {
		M[0] = M[0] * M[i];
	}
	M[0] = power(M[0], 1LL*D / T);
	for (int i = 1; i <= D % T; i++)
		M[0] = M[0] * M[i];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << M[0].v[i][j] << " ";
		}
		cout << "\n";
	}
}

---

행렬의 중요성...

선형대수학의 중요성...