[BOJ 1533 // C++] 길의 개수

 

 

www.acmicpc.net/problem/1533

1533번: 길의 개수

이 문제는 S에서 출발하여 T분 뒤에 E에 도착하는 경우의 수를 구하는 문제이다.

여기서 이 그래프의 각 간선에 가중치가 0~5까지 설정되어있으므로 그 경우를 나눠서 계산하자.

 

다음은 이 문제를 풀기 위한 행렬 mat을 block matrix로 표현한 것이다. 각 block은 N by N 행렬이다.

a_i -> a_(i+1) 경로수	a_(i-1) -> a_(i+1) 경로수	a_(i-2) -> a_(i+1) 경로수	a_(i-3) -> a_(i+1) 경로수	a_(i-4) -> a_(i+1) 경로수
a_i를 옮김	0	0	0	0
0	a_(i-1)을 옮김	0	0	0
0	0	a_(i-2)를 옮김	0	0
0	0	0	a_(i-3)를 옮김	0

이 행렬을 곱할 벡터 vec의 초기값은 다음과 같다. 각 block의 성분은 N개이다.

a_0: 시작점만 1, 나머지 점은 0

0

0

0

0

이렇게 설정하면 mat의 T제곱을 vec에 곱해 나온 첫 블럭은 점 S에서 출발해 점 1~N까지 도달하는 경우의 수를 담게 된다. mat의 T제곱은 binary exponentiation을 통해 빠르게 계산할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;

long long mat[60][50];
long long tempmat[50][50];
long long vec[50];
long long tempvec[50];

int main()
{
    int N, S, E, T;
    cin >> N >> S >> E >> T;
    vec[S - 1] = 1; // 시작점 초기값 1, 나머지 0
    string x;
    for (int i = 0;i < N;i++) {
        cin >> x;
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 1인 성분들
            if (x[j] == '1') {
                mat[j][i] = 1;
            }
        }
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 2인 성분들
            if (x[j] == '2') {
                mat[j][i + N] = 1;
            }
        }
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 3인 성분들
            if (x[j] == '3') {
                mat[j][i + 2 * N] = 1;
            }
        }
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 4인 성분들
            if (x[j] == '4') {
                mat[j][i + 3 * N] = 1;
            }
        }
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 5인 성분들
            if (x[j] == '5') {
                mat[j][i + 4 * N] = 1;
            }
        }
    }
    for (int i = 0;i < 5 * N;i++) { // 지나간 네 개의 경우를 아래로 옮김
        mat[i + N][i] = 1;
    }

    while (T > 0) { // binary exponentiation
        if (T & 1) {
            for (int i = 0; i < 5 * N; i++) {
                for (int k = 0; k < 5 * N; k++) {
                    tempvec[i] += mat[i][k] * vec[k];
                }
            }
            for (int i = 0; i < 5 * N; i++) {
                vec[i] = tempvec[i] % 1000003;
                tempvec[i] = 0;
            }
        }

        for (int i = 0; i < 5 * N; i++) {
            for (int j = 0; j < 5 * N; j++) {
                for (int k = 0;k < 5 * N;k++) {
                    tempmat[i][j] += mat[i][k] * mat[k][j];
                }
            }
        }
        for (int i = 0; i < 5 * N; i++) {
            for (int j = 0; j < 5 * N; j++) {
                mat[i][j] = tempmat[i][j] % 1000003;
                tempmat[i][j] = 0;
            }
        }

        T >>= 1;
    }

    cout << vec[E - 1]; // E번 노드까지 가는 경로의 수

    return 0;
}