[백준 1533] 길의 개수

인접 행렬을 제곱한다는 참신한 아이디어를 알게된 문제.

1. 풀이

이 문제를 보고 어떻게 풀어야 되는지 모르기 때문에 막 이리저리 dp로 하고 있었다. 하지만 아무리 해도 모든 경우의 수를 고려하는 식을 짜기 힘들었는데, 질문 게시판에 인접행렬을 제곱해서 푸는 문제라고 나와 있어 공부해보 았다.

인접행렬을 제곱하는 의미에 대해서는 이전에 작성한 글을 참고하기 바란다.

위의 글처럼 가중치가 있는 그래프가 주어지지만 가중치가 적기 때문에 각 정점마다 최대 \(4\)개의 정점을 추가적으로 만들어 가중치가 없는 그래프를 만들 수 있고, 적절하게 행렬 제곱을 해주면 된다.

2.소스 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;


typedef vector<vector<ll>> Mat;
const ll MOD = 1000000LL + 3LL;


Mat mul(Mat a, Mat b) {
    Mat ans;
    ans.resize(a.size(), vector<ll>(b[0].size()));
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < b[i].size(); j++) {
            ll& ret = ans[i][j];
            for (int k = 0; k < b.size(); k++)
                ret = (ret + a[i][k] * b[k][j]) % MOD;
        }


    return ans;
}


Mat pow(Mat a, ll cnt) {
    if (cnt == 1) return a;
    Mat mid = pow(a, cnt / 2);
    if (cnt % 2) return mul(mul(mid, mid), a);
    else return mul(mid, mid);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);


    ll n, s, e, t; cin >> n >> s >> e >> t;
    Mat mat;
    mat.resize(5 * n, vector<ll>(5 * n));
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= 4; j++)
            mat[5 * i+j-1][5 * i + j] = 1;


    for (int i = 0; i < n; i++) {
        string str; cin >> str;
        for (int j = 0; j < n; j++) {
            int num = str[j] - '0';
            if (num > 0)
                mat[5 * i + num - 1][5 * j] = 1;
        }
    }


    Mat ret = pow(mat, t);
    ll ans = ret[5 * (s - 1)][5 * (e - 1)];


    cout << ans;


    return 0;
}