[백준 17401] 일하는 세포

 

 분할 정복으로 행렬의 거듭제곱을 구하는 문제. 문제를 유심히 보다 보니, 예전에 풀었던 본대 산책2 문제와 상당히 비슷했다.

 

[백준 12850] 본대 산책2

[백준 12850] 본대 산책2

 

 물론 이번에는, 인접 행렬이 특정 사이클에 따라 바뀐다는 것이 달랐지만 큰 틀에서는 달라질 게 없었다. 특정 노드 i에서 j로 이동할 수 있는 경우의 수가 결국 행렬 곱 matrix[i][j]를 구한 것과 같다는 점에서 시작한다. 따라서 두 행렬의 곱을 구하는 함수를 만들어 주었다.

 

 대신에 이 문제에서도 D의 값이 10^9까지 들어올 수 있는데, 그렇게 되면 행렬 곱을 10^9번이나 해주어야 하고 시간초과가 날 것이다. 이때 이용하기 좋은 것은 거듭제곱 꼴을 분할 정복으로 처리하는 것이고, 그래서 특정 행렬을 거듭제곱하는 함수도 구현해 주었다.

 

 이후에는 심플한 문제로 바뀌는데, 사이클의 크기인 T 값을 이용해서 D초 동안 온전한 사이클 d회와 남은 시간(마지막 사이클 이후에 필요한 적혈구의 이동 필요 횟수이자 나머지) r을 구할 수 있기 때문이다. 혈관 지도 사이클을 한 차례 모두 돌렸을 때의 혈관 이동 경우의 수를 행렬 곱으로 구해주고, 도중에 모든 사이클 처리 이후 추가적으로 곱해줄 나머지 r에 해당하는 행렬도 저장해 둔다. 

 한 사이클을 모두 돌았을 때 가능한 경로의 수를 구한 행렬을 계산해 냈다면, 사이클이 반복되는 d회만큼 해당 행렬이 거듭제곱될 것이므로 작성해 둔 행렬 거듭제곱 함수에 넣어서 구해준다. 그리고 그 결과물을 나머지 행렬과 곱해서 최종적인 D시점의 이동 가능 경로 행렬을 구해내면 끝이다.

 

 본대 산책2 문제를 풀어봤기에 어렵지 않게 접근할 수 있었던 문제. 대신 구현은 실수하기 좋은 부분들이 조금 있는 것 같다.

 

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

int t, n, d;

vector<vector<int> > multiMatrix(vector<vector<int> >& a, vector<vector<int> >& b) {
    vector<vector<int> > result(n+1, vector<int>(n+1, 0));
    for(int i=1; i<=n ; i++) {
        for(int j=1; j<=n; j++) {
            long long sum = 0;
            for(int k=1; k<=n; k++) {
                sum += ((long long)a[i][k]%MOD * (long long)b[k][j]%MOD) % MOD;
                sum %= MOD;
            }
            result[i][j] = sum;
        }
    }

    return result;
}

vector<vector<int> > powerMatrix(vector<vector<int> >& mat, int exp) {
    if(exp==1) return mat;

    vector<vector<int> > half = powerMatrix(mat, exp/2);
    vector<vector<int> > result = multiMatrix(half, half);
    if(exp%2 == 0) {
        return result;
    } else {
        return multiMatrix(result, mat);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t >> n >> d;

    vector<vector<int> > all(n+1, vector<int>(n+1, 0));
    vector<vector<int> > result(n+1, vector<int>(n+1, 0));
    vector<vector<int> > remain(n+1, vector<int>(n+1, 1));

    for(int i=1; i<=n; i++) {
        all[i][i] = 1;
        result[i][i] = 1;
    }

    for(int i=0; i<t; i++) {
        int m, a, b, c;
        cin >> m;

        vector<vector<int> > temp(n+1, vector<int>(n+1, 0));

        for(int j=0; j<m; j++) {
            cin >> a >> b >> c;
            temp[a][b] = c;
        }

        if(d%t == i) {
            remain = all;
        }
        all = multiMatrix(all, temp);
    }

    if(d/t != 0) {
        result = powerMatrix(all, d/t);
    }

    result = multiMatrix(result, remain);

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cout << result[i][j] << " ";
        }
        cout << "\n";
    }
}