[BOJ 12850 | C++] 본대 산책2 :: 행렬 거듭제곱

BOJ

[BOJ 12850 | C++] 본대 산책2 :: 행렬 거듭제곱

yeonee911 2025. 2. 11. 00:16

문제 링크 : https://www.acmicpc.net/problem/12850
문제 태그 : 수학, 그래프 이론, 분할 정복을 이용한 거듭제곱

풀이

그래프 구성 전처리 하는게 귀찮은 작업이었습니다...

그리고 제가 재귀😵‍💫를 너무 못해서 행렬 거듭제곱 작업이 어려웠습니다o(TヘTo) 당분간 백준에서 재귀 문제집만 풀어야겠다는 생각도 했습니다...

⚡행렬 곱셈과 경로의 상관관계

행렬 A와 행렬 B가 있다고 합시다. 행렬 A의 크기는 i × k, 행렬 B의 크기는 k × j이며, 행렬 곱셈이 성립하려면 A의 열 개수와 B의 행 개수가 같아야 합니다.

이때 행렬 곱셈의 결과로 행렬 C가 만들어진다고 할 때 C의 크기는 i × j가 됩니다.

여기까지는 철저히 행렬 곱셈의 정의입니다.

그런데 각 행과 열을 그래프의 정점으로 생각해 봅시다. 즉, 행렬 A, B, C는 그래프를 인접 행렬 형태로 표현한 것입니다. 행렬 곱셈을 수행하면 i에서 k를 거쳐 j로 가는 모든 경로의 개수를 계산할 수 있습니다. 이는 k를 바꿔 가면서 i에서 j까지의 모든 경로를 고려하는 과정과 동일합니다.

즉, 행렬 곱셈을 통해 두 정점 와 j 사이의 가능한 모든 경로의 개수를 구할 수 있는 것입니다.

#include <iostream>
#include <vector>

using namespace std;
const int MAX = 1000000;


// 행렬 곱셈
vector<vector<long long>> matrix_mul(const vector<vector<long long>>& a, const vector<vector<long long>>& b) {
	vector acc(8, vector(8, 0LL));
	for (int i = 0;i < 8;i++) {
		for (int j = 0;j < 8;j++) {
			for (int k = 0;k < 8;k++) {
				acc[i][j] += a[i][k] * b[k][j];
			}
			acc[i][j] %= 1000000007;
		}
	}
	return acc;
}

vector<vector<long long>> recursive(vector<vector<long long>>& a, int n) {
	if (n == 1) return a;
	vector<vector<long long>> b = recursive(a, n / 2);
	b = matrix_mul(b, b);
	if (n & 1) b = matrix_mul(b, a);
	return b;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// 정보과학관 0
	// 전산관 1
	// 미래관 2
	// 신양관 3
	// 한경직기념관 4
	// 진리관 5
	// 학생회관 6
	// 형남공학관 7
	vector g(8, vector(8, 0LL));
	g[0][1] = 1; g[1][0] = 1;
	g[0][2] = 1; g[2][0] = 1;
	g[1][2] = 1; g[2][1] = 1;
	g[1][3] = 1; g[3][1] = 1;
	g[2][3] = 1; g[3][2] = 1;
	g[2][4] = 1; g[4][2] = 1;
	g[3][4] = 1; g[4][3] = 1;
	g[3][5] = 1; g[5][3] = 1;
	g[4][5] = 1; g[5][4] = 1;
	g[5][6] = 1; g[6][5] = 1;
	g[4][7] = 1; g[7][4] = 1;
	g[6][7] = 1; g[7][6] = 1;
	

	int d;
	cin >> d;
	auto ans = recursive(g, d);
	cout << ans[0][0];
}

재귀를 너무 못해서(ㅠㅠ) recursive 함수는 jinhan814님의 도움을 받았습니다(●'◡'●)