[백준] BOJ 1533 : 길의 개수

https://www.acmicpc.net/problem/1533

1533번: 길의 개수

먼저 이 문제의 조건을 읽어봅시다.

 

1. 교차로의 개수(= 노드의 개수) 및 시작점과 끝점이 주어지고 기다릴 시간이 주어집니다.

2. 그리고 인접행렬이 주어지는데, 0이면 길이 없는 것이고, 1 이상이면 해당 값만큼의 시간을 들여 노드 간을 이동할 수 있습니다.

3. 문제에서는 시작점에서 시작해서 끝점에서 끝나는 경로들 중에서 이동하는데 총 걸리는 시간이 기다릴 시간만큼 드는 경로들의 개수를 구하여야 합니다.

 

먼저, 제일 처음에 이 문제를 읽었을 때는 도대체 어떻게 풀어야할지 몰랐습니다. 그래서 접근 방법도 안 떠올라서 묵혀두었다가 우연히 BOJ 12916를 풀게 되었습니다.

https://www.acmicpc.net/problem/12916

12916번: K-Path

이 문제는 다음과 같이 풀 수 있습니다. (이 문제가 주 문제가 아니므로 간략하게만 설명하겠습니다.)

 

1. 인접행렬은 그냥 기본적으로 이동했을 때에 이동 방법의 개수가 됩니다. m[i][j]가 1이면 1가지, 아니면 0가지의 방법으로 갈 수 있다는 것이죠.

2. 그리고 만약에 중간에 하나를 거쳐가야 한다면 다음과 같이 계산할 수 있습니다. m'[i][j] = sum(m[i][k]+m[k][j]) 이렇게 되면 두 번  이동했을 때 i에서 j로 갈 수 있는 경우의 수가 됩니다.

3. 그리고 m''를 세 번 이동했을 때에 경우의 수들을 담고 있는 인접행렬이라면, sum(m'[i][k] + m''[k][j])는 2번 + 3번 이동한 경우의 수로 총 다섯 번 이동했을 때의 i에서 j로 갈 수 있는 경우의 수가 됩니다.

4. 그리고 계산식을 잘 보시면 알겠지만 행렬의 곱입니다.

 

그래서 이 문제는 사실상 인접행렬가지고 K번 거듭제곱하는 문제였습니다. 그리고 우리는 이를 분할정복을 활용하여 O(logK)만에 구할 수 있습니다. 그래서 빨리 풀어서 AC를 맞았으면서 이번에 다룰 문제의 해도 어느정도 윤곽이 드러났습니다. 그래프를 수정하여 k분이 걸리는 거리라면 실제로 총 k번 동안 이동해야 목적지로 가도록 한다면? 이번 문제도 이렇게 풀 수 있겠지요?

 

그렇게 풀려고 했는데, 그래프 모델링에서 좀 난관을 겪었습니다. 그냥 별 생각없이 각 노드별로 이동하는 노드들을 따로따로 만들어주니 인접행렬의 크기가 매우 커졌습니다. 그래서 내부적으로 돌려보았을 때는 당연히 시간초과도 나고 그랬습니다만, 결국에는 각 노드별로 5,4,3,2분 정도 걸릴 때 들어가는 노드들을 따로 따로 만들어서 5N*5N 인접행렬을 만들 수 있었습니다. 이외에는 그냥 행렬 거듭제곱을 O(logT)만에 구해서 답을 맞추었습니다.

 

아래는 제 코드입니다. 총 시간복잡도는 O(N^3logT)였습니다. 저는 행렬 크기를 5N이 아니라 편의상 60으로 고정하고 풀었는데, 이래도 시간 내에 충분히 돌아갔습니다.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll m[60][60];
ll new_m[60][60];
ll ans[60][60];
ll MOD = 1'000'003;

void matrix_modification(ll n){
    for(int i =0; i<n; ++i){
        m[40+i][30+i] = m[30+i][20+i] = m[20+i][10+i] = m[10+i][i] = 1;
        for(int j =0; j<n; ++j){
            if(m[i][j] == 2){
                m[i][j] = 0;
                m[i][10+j] = 1;
            }
            else if(m[i][j] == 3){
                m[i][j] = 0;
                m[i][20+j] = 1;
            }
            else if(m[i][j] == 4){
                m[i][j] = 0;
                m[i][30+j] = 1;
            }
            else if(m[i][j] == 5){
                m[i][j] = 0;
                m[i][40+j] = 1;
            }
        }
    }
    return ;
}

ll mul(ll t, ll s, ll e){
    while(t){
        if(t%2){
            for(int i =0; i<60; ++i){
                for(int j =0; j<60; ++j){
                    for(int k =0; k<60; ++k){
                        new_m[i][j] += ans[i][k]*m[k][j];
                        new_m[i][j] %= MOD;
                    }
                }
            }
            for(int i =0; i<60; ++i){
                for(int j =0; j<60; ++j){
                    ans[i][j] = new_m[i][j];
                    new_m[i][j] = 0;
                }
            }
        }
        
        for(int i =0; i<60; ++i){
            for(int j =0; j<60; ++j){
                for(int k=0; k<60; ++k){
                    new_m[i][j] += m[i][k] * m[k][j];
                    new_m[i][j] %= MOD;
                }
            }
        }
        for(int i =0; i<60; ++i)
            for(int j =0; j<60; ++j){
                m[i][j] = new_m[i][j];
                new_m[i][j] = 0;
            }
    
        t/=2;
    }
    
    return ans[s][e];
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll N, S, E, T;
    cin >> N >> S >> E >> T;
    for(int i =0; i<N; ++i){
        for(int j =0; j<N; ++j){
            char ch;
            cin >> ch;
            m[i][j] = ch-'0';
        }
    }
    matrix_modification(N);
    
    for(int i = 0; i<60; ++i)
        ans[i][i] = 1;
    
    cout << mul(T,S-1,E-1);
    
    return 0;    
} // Math, Graphs, Divide and Conquer for matrix multiplication

 

이렇게 제가 다이아 5를 달성한 문제를 한 번 리뷰해보았습니다. 제가 오랜만에 풀이 글을 올려보는지라 좀 어색했는데, 그래도 해본 경험이 있어서인지 좀 수월하게 작성할 수 있었습니다. 인접행렬의 곱을 활용해서 길의 개수를 세는 문제였는데, 이걸 또 활용해서 사실 경로의 길이가 K까지만 가능할 때의 최단거리 등등도 구할 수 있습니다. (바로 BOJ 29695 제가 예전에 낸 기지방호 문제가 그렇게도 풀립니다. 물론 정해는 아닙니다!) 그래서 인접행렬 곱을 활용해서 푸는 문제들은 좀 더 연구해보고 싶기도 합니다.