백준 12850. 본대 산책2(C++)

12850. 본대 산책2

12850번: 본대 산책2

---

입력

• 산책하는 시간 D분이 주어진다.(1 <= D <= 1,000,000,000)

---

문제 풀이

• 문제에 캠퍼스 지도가 주어져 있다. 주어진 캠퍼스 지도를 이용하여 인접 리스트 또는 인접 행렬을 만들어 문제를 풀이할 수 있다.
• 기본적으로 DFS와 BFS를 이용하여 풀이를 할 수 있을 것 같다.
• 하지만 실제로 위와 같은 방법으로 접근을 한다면 D의 범위가 제법 크기 때문에 시간 초과를 피하지 못할 것이다.
• 따라서 다른 방법을 생각해야한다.
• 인접 행렬을 거듭제곱하면 곱한 수만큼 경로를 거쳤을 때 각 노드에서 노드로 가는 경로의 수가 나온다는 것을 알 수 있다.
• 그러면 최악의 경우 1,000,000,000번을 곱해야 하는데, 마찬가지로 시간 초과에 직면하게 된다.
• 따라서 분할정복 개념을 도입해서 거듭제곱을 해줘야한다.
• 아래는 작성한 코드이다.

#include <iostream>
#include <vector>

#define MOD 1000000007

long long D;
std::vector<std::vector<long long>> path(8, std::vector<long long>(8));
std::vector<std::vector<long long>> result(8, std::vector<long long>(8));

std::vector<std::vector<long long>> mat_mul(std::vector<std::vector<long long>> a1, std::vector<std::vector<long long>> a2) {
	std::vector<std::vector<long long>> a3(8, std::vector<long long>(8));
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			long long tmp = 0;
			for (int k = 0; k < 8; k++) {
				tmp += (a1[i][k] * a2[k][j]) % MOD;
				tmp = tmp % MOD;
			}
			a3[i][j] = tmp;
		}
	}
	return a3;
}

int main()
{
	std::cin >> D;

		
	path = {{0, 1, 1, 0, 0, 0, 0, 0},
			{1, 0, 1, 1, 0, 0, 0, 0},
			{1, 1, 0, 1, 1, 0, 0, 0},
			{0, 1, 1, 0, 1, 1, 0, 0},
			{0, 0, 1, 1, 0, 1, 1, 0},
			{0, 0, 0, 1, 1, 0, 0, 1},
			{0, 0, 0, 0, 1, 0, 0, 1},
			{0, 0, 0, 0, 0, 1, 1, 0} };

	for (int i = 0; i < 8; i++) {
		result[i][i] = 1;
	}

	while (D > 0) {
		if (D % 2) {
			result = mat_mul(result, path);
		}
		D = D / 2;
		path = mat_mul(path, path);
	}

	std::cout << result[0][0];

	return 0;
}