BOJ 12850 - 본대 산책2

문제

• 노드가 8개이고 간선의 가중치가 1인 그래프의 그림과 \(D(1 \le D \le 1,000,000,000)\)가 주어질 때, 고정된 0번 노드에서 길이가 D인 closed walk의 개수를 1000000007으로 나눈 나머지를 출력해야 한다.

풀이

• 그래프의 연결 정보를 인접 행렬 \(A\)로 표현했을 때, \(A^k\)의 원소 \(a_{ij}\)는 길이가 \(k\)이고 \(i \rightarrow j\)인 walk의 개수이다.
• \(O(N)\)도 TLE이기 때문에, 제곱을 구할 때 \(O(log^N)\)으로 구해야 한다.

코드

#include <iostream>
#include <vector>
#define v vector
#define NODE 8
#define MOD 1000000007

using namespace std;
using vi = vector<int>;
using ll = long long;

v<v<ll>> mul(v<v<ll>>& m1, v<v<ll>>& m2) {
    int n = m1.size();
    v<v<ll>> res(n, v<ll>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                res[i][j] = (res[i][j] + m1[i][k] * m2[k][j]) % MOD;
            }
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int d;
    cin >> d;
    v<v<ll>> r(NODE, v<ll>(NODE, 0)), adj = {{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, 0, 1},
                                             {0, 0, 0, 1, 1, 0, 1, 0},
                                             {0, 0, 0, 0, 0, 1, 0, 1},
                                             {0, 0, 0, 0, 1, 0, 1, 0}};
    for (int i = 0; i < NODE; i++) r[i][i] = 1;
    while (d) {
        if (d & 0x01) r = mul(r, adj);
        d >>= 1;
        adj = mul(adj, adj);
    }
    cout << r[0][0] << endl;
    return 0;
}

풀고나서

• 그래프와 행렬의 관계를 다시 공부할 수 있었다.