백준 12850번: 본대 산책2

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

12850번: 본대 산책2

---

이 문제는 인접행렬의 형태가 정해져 있습니다.

 

그걸 그대로 구현해서, $D$ 제곱하여 정보과학관에서 정보과학관으로 가는 경로의 수를 출력하면 됩니다.

 

저의 경우, 위 그래프를 다음과 같이 재구성했습니다.

 

재구성된 그래프. 각 정점에 대한 설명은 이하 내용 참고

 

이 그림에서 각 번호에 대응하는 건물은 다음과 같습니다.

 

0 : 정보과학관

1 : 전산관

2 : 미래관

3 : 신양관

4 : 한경직기념관

5 : 진리관

6 : 형남공학관

7 : 학생회관

 

그 결과, 인접행렬은 다음과 같았습니다. (당연히 경로에 방향이 없으므로 symmetric 한 matrix가 됩니다.)

 

$\begin{bmatrix} 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 \end{bmatrix}$

 

이를 $D$ 제곱하면 끝이고 제 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 1000000007

typedef struct {
	long long array[8][8];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix Base, long long power);

int main() {
	
	Matrix Base = 
	{
	{
		{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}
	}
	};
	
	long long D;
	scanf("%lld", &D);
	
	Base = matrix_power_modular (Base, D);
	
	printf("%lld", Base.array[0][0]);
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B) {
	Matrix result = { {{0}} };
	for (int i = 0; i < 8; i++) {
		for (int k = 0; k < 8; k++) {
			for (int j = 0; j < 8; j++) {
				result.array[i][j] = (result.array[i][j] + A.array[i][k] * B.array[k][j]) % mod;
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix Base, long long power) {
	Matrix result = { {{0}} };
	for (int i = 0; i < 8; i++) {
		result.array[i][i] = 1;
	}
	while(power) {
		if (power % 2) {
			result = matrix_multiply_modular (result, Base);
		}
		Base = matrix_multiply_modular (Base, Base);
		power /= 2;
	}
	return result;
}

(C11, 1116KB, 0ms, 제출번호 31680550)

---