[C++] BOJ 12850 - 본대 산책2

BOJ 12850 - 본대 산책2 (https://www.acmicpc.net/problem/12850)

01. 🔎 문제 탐색

D: 준영이가 산책할 시간 (D분)
한 건물에서 인접한 다른 건물로 이동하는 시간 1분

캠퍼스의 지도가 위와 같을 때, 정보과학관에서 시작하여 D분이 될 때 정보과학관으로 도착 가능한 경로의 수를 출력

01-1. 가능한 시간 복잡도

• D의 최대가 1e9로 시간 복잡도 $O(log D)$이하로 구현

01-2. 알고리즘 선택

• 분할 정복을 이용한 전이 행렬의 거듭제곱으로 구현

02. 📝 코드 설계하기

각 노드(건물)에 번호를 붙여, 갈 수 있는 인접한 건물을 나타내면 아래와 같다.

정보과학관 (1)	2	4
전산관 (2)	1	3	4
신양관 (3)	2	4	5	6
미래관 (4)	1	2	3	6
진리관 (5)	3	6	7
한경직기념관 (6)	3	4	5	8
학생회관 (7)	5	8
형남공학관 (8)	6	7

처음 출발은 정보과학관이다. 0분(D=0) 일때, 각 건물에 갈 수 있는 경로는 아래와 같다.
$V(0) = [1, 0, 0, 0, 0, 0, 0, 0]$
그리고 1분이 지났을 때는, 정보과학관에서 갈 수 있는 곳에 도착해있을 것이다.
$V(1) = [0, 1, 0, 1, 0, 0, 0, 0]$
2분이 지났을 때, 정보과학관으로 돌아오는 루트는 1 > 2 > 1 과 1 > 4 > 1 로 2가지가 될 것이다.
$V(2) = [2, 1, 2, 1, 0, 1, 0, 0]$

위의 과정을 행렬식으로 나타내면 아래와 같다.
$$
V(D+1) = 
\begin{bmatrix}
0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 
\end{bmatrix} * 
V(D)
$$

편의상 전이 행렬을 A로 치환하여 보자.

 

$V(1) = A \cdot V(0)$  
$V(2) = A \cdot V(1) = A^2 \cdot V(0)$  
$V(3) = A \cdot V(2) = A^3 \cdot V(0)$  
$\therefore V(D) = A^D \cdot V(0)$

 

이를 코드로 설계해보면,

1. 전이 행렬(각 건물의 인접한 건물을 2차원 vector로 나타낸 것) A 초기화
2. 행렬 A에 D만큼 제곱 수행
   
   1. 행렬 A에 D / 2를 제곱한 행렬을 재귀적으로 곱해줌
      $(A * A \rightarrow A^2 * A^2 ... \rightarrow A^{D/2} * A^{D/2} = A^D)$
3. $A^D$행렬의 (0, 0) 위치의 값은 정보과학관(0번 정점)에 다시 도달하는 경로 수를 나타냄

 

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;

const ll MOD = 1e9+7;

matrix operator*(const matrix& a, const matrix& b){
  const int N = a.size(), M = b.size(), K = b[0].size();
  matrix res = matrix(N, vector<ll>(K, 0));

  for(int i = 0; i < N; i++)
    for(int j = 0; j < K; j++)
      for(int l = 0; l < M; l++)
        res[i][j] = (res[i][j] + a[i][l] * b[l][j]) % MOD;

  return res;
}

matrix pow(matrix a, ll n){
  if(n == 1) return a;

  matrix half = pow(a, n / 2);
  matrix res = half * half;
  if(n % 2 == 1) res = res * a;

  return res;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  ll D; cin >> D;
  matrix A = {
    {0, 1, 0, 1, 0, 0, 0, 0},
    {1, 0, 1, 1, 0, 0, 0, 0},
    {0, 1, 0, 1, 1, 1, 0, 0},
    {1, 1, 1, 0, 0, 1, 0, 0},
    {0, 0, 1, 0, 0, 1, 1, 0},
    {0, 0, 1, 1, 1, 0, 0, 1},
    {0, 0, 0, 0, 1, 0, 0, 1},
    {0, 0, 0, 0, 0, 1, 1, 0}
  };

  cout << pow(A, D)[0][0] << "\n";

  return 0;
}