백준 1533 길의 개수 (c++) : 피너클

1533번: 길의 개수

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

 

행렬을 이용한 거듭제곱으로 풀었다.

이 문제를 풀기전에

12850번: 본대 산책2

대충 이런 문제를 풀고오면 쉽다.

 

matrix[1][2] = 1 이라면 1에서 2로 가는 길이 있다는 의미다.

matrix[2][3] = 0 이라면 2에서 3으로 가는 길이 없다는 의미다.

 

이를 기본으로 생각해보자.

문제에서는 5이하의 숫자로 입력이 들어온다.

matrix[1][2] = 5라면 1에서 2까지 가는데 5의 시간이 걸린다는 의미이다.

이걸 조금만 변형할것이다.

정점은 무조건 5를 곱한 수로 생각한다.

이전에 matrix[1][2] = 1이었다면

이제는 matrix[1 * 5][2 * 5] = 1으로 생각하는 것이다.

이러면 

	0	1
0	0	1
1	1	0

대충 위처럼 생겼던 그래프가

	0	5
0	0	1
5	1	0

위처럼 변형된다. 바뀐거는 인덱스의 숫자다. 

준비는 끝났다.

long long n, s, e, t;
long long matrix[51][51];
long long MOD = 1000003;
vector<vector<long long>> graph;

사용할 변수들이다.

	cin >> n >> s >> e >> t;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			char c;
			cin >> c;
			int a = c - '0';

전부다 입력을 받아준다.

int a는 i에서 j까지 가는데 얼마나 걸리는지이다.

a == 1이라면 1만큼 걸리는거고 2라면 2만큼 걸리는거다.

이제 이부분을 노가다로 채워줄것이다.

			if (a == 1) {
				matrix[5 * i][5 * j] = 1;
			}

a == 1이라면 바로 가지는 것이다. matrix[5 * i][5 * j] = 1

이렇게 하면 5 * i에서 5 * j로 갈수있다는 의미이다.

			else if (a == 2) {
				matrix[5 * i][5 * j + 1] = 1;
				matrix[5 * j + 1][5 * j] = 1;
			}

a == 2라면 바로는 못간다. 그러니 다른곳을 거쳐서 갈것이다.

matrix[5 * i][5 * j + 1] = 1

5 * i에서 바로 5 * j로 가는것이 아닌 다른곳을 거쳐서 간다. 그게 5 * j + 1이다.

저곳을 거쳐서 감으로서 시간이 2만큼 걸리는걸 구현한 것이다.

			else if (a == 3) {
				matrix[5 * i][5 * j + 2] = 1;
				matrix[5 * j + 2][5 * j + 1] = 1;
				matrix[5 * j + 1][5 * j] = 1;
			}
			else if (a == 4) {
				matrix[5 * i][5 * j + 3] = 1;
				matrix[5 * j + 3][5 * j + 2] = 1;
				matrix[5 * j + 2][5 * j + 1] = 1;
				matrix[5 * j + 1][5 * j] = 1;
			}
			else if (a == 5) {
				matrix[5 * i][5 * j + 4] = 1;
				matrix[5 * j + 4][5 * j + 3] = 1;
				matrix[5 * j + 3][5 * j + 2] = 1;
				matrix[5 * j + 2][5 * j + 1] = 1;
				matrix[5 * j + 1][5 * j] = 1;
			}
		}
	}

이걸 노가다로 채워주면 된다.

노가다로 채운 이유는 노가다로 채우는거 말고는 아이디어가 생각나지 않아서이다.

 

	for (int i = 0; i < 5 * n; i++) {
		vector<long long> tmp;
		for (int j = 0; j < 5 * n; j++) {
			tmp.push_back(matrix[i][j]);
		}
		graph.push_back(tmp);
	}

	cout << solve(t) << '\n';
}

그 후에는 행렬을 이용해서 거듭제곱해주면 된다.

vector<vector<long long>> mmatrix(vector<vector<long long>> a, vector<vector<long long>> b) {
	vector<vector<long long>> v(5 * n, vector<long long>(5 * n, 0));
	for (int i = 0; i < 5 * n; i++) {
		for (int j = 0; j < 5 * n; j++) {
			for (int k = 0; k < 5 * n; k++) {
				v[i][j] = (v[i][j] + a[i][k] * b[k][j]) % MOD;
			}
		}
	}
	return v;
}

long long solve(long long time) {
	vector<vector<long long>> result(5 * n, vector<long long>(5 * n, 0));
	for (int i = 0; i < 5 * n; i++) result[i][i] = 1;

	while (time > 0) {
		if (time % 2 == 0) {
			graph = mmatrix(graph, graph);
			time /= 2;
		}
		else {
			result = mmatrix(graph, result);
			time -= 1;
		}
	}
	return result[(s-1) * 5][(e-1) * 5] % MOD;
}

이게 행렬을 이용한 거듭제곱 코드다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <tuple>
#include <queue>
#include <string>

using namespace std;

long long n, s, e, t;
long long matrix[51][51];
long long MOD = 1000003;
vector<vector<long long>> graph;

vector<vector<long long>> mmatrix(vector<vector<long long>> a, vector<vector<long long>> b) {
	vector<vector<long long>> v(5 * n, vector<long long>(5 * n, 0));
	for (int i = 0; i < 5 * n; i++) {
		for (int j = 0; j < 5 * n; j++) {
			for (int k = 0; k < 5 * n; k++) {
				v[i][j] = (v[i][j] + a[i][k] * b[k][j]) % MOD;
			}
		}
	}
	return v;
}

long long solve(long long time) {
	vector<vector<long long>> result(5 * n, vector<long long>(5 * n, 0));
	for (int i = 0; i < 5 * n; i++) result[i][i] = 1;

	while (time > 0) {
		if (time % 2 == 0) {
			graph = mmatrix(graph, graph);
			time /= 2;
		}
		else {
			result = mmatrix(graph, result);
			time -= 1;
		}
	}
	return result[(s-1) * 5][(e-1) * 5] % MOD;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> s >> e >> t;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			char c;
			cin >> c;
			int a = c - '0';

			if (a == 1) {
				matrix[5 * i][5 * j] = 1;
			}
			else if (a == 2) {
				matrix[5 * i][5 * j + 1] = 1;
				matrix[5 * j + 1][5 * j] = 1;
			}
			else if (a == 3) {
				matrix[5 * i][5 * j + 2] = 1;
				matrix[5 * j + 2][5 * j + 1] = 1;
				matrix[5 * j + 1][5 * j] = 1;
			}
			else if (a == 4) {
				matrix[5 * i][5 * j + 3] = 1;
				matrix[5 * j + 3][5 * j + 2] = 1;
				matrix[5 * j + 2][5 * j + 1] = 1;
				matrix[5 * j + 1][5 * j] = 1;
			}
			else if (a == 5) {
				matrix[5 * i][5 * j + 4] = 1;
				matrix[5 * j + 4][5 * j + 3] = 1;
				matrix[5 * j + 3][5 * j + 2] = 1;
				matrix[5 * j + 2][5 * j + 1] = 1;
				matrix[5 * j + 1][5 * j] = 1;
			}
		}
	}

	for (int i = 0; i < 5 * n; i++) {
		vector<long long> tmp;
		for (int j = 0; j < 5 * n; j++) {
			tmp.push_back(matrix[i][j]);
		}
		graph.push_back(tmp);
	}

	cout << solve(t) << '\n';
}

전체코드다.