[BOJ] 12850번 - 본대 산책2

백준 12850번 - 본대 산책2

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	638	502	435	83.493%

문제

숭실 대학교 정보 과학관은 유배를 당해서  캠퍼스의 길 건너편에 있다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 꽃 이 활짝 핀 본 대를 선망한다. 어느 날 준영이는 본 대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.

(편의 상 문제에서는 위 건물만 등장한다고 가정하자)

한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.

입력

D 가 주어진다 (1 ≤ D ≤ 1,000,000,000) 

출력

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.

---

예제 입력 1

100000000

예제 출력 1

261245548

출처

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

12850번: 본대 산책2

알고리즘 분류

• 수학
• 그래프 이론
• 분할 정복을 이용한 거듭제곱

접근 방법

N의 범위를 보기 이전에는 전형적인 그래프 탐색 문제라 생각을 했던 문제였다.

다만, N의 범위가 ${10^9}$ 를 넘어가는 만큼 O(N) 방식의 탐색 또한 TLE임을 알 수 있다.

 

문제를 풀기 앞 서, 인접행렬로 그래프를 표현하였을 때 특징을 알아보자.

설명의 편의를 위해 정점 A,B에 대한 크기가 2인 인접행렬을 살펴보자.

 

 

AA	AB
BA	BB

 

이를 제곱할 경우 새로운 2*2 행렬은 다음과 같다.

AAAA + ABBA	AAAB + ABBB
BAAA + BBBA	BAAB + BBBB

 

초기 2*2행렬의 원소 ${K_1K_2}$를 ${K_1}$ -> ${K_2}$로 가는 경우의 수로 정의를 할 경우

이를 제곱한 새로운 행렬의 원소 ${K_1K_2 + K_3K_4}$ 는 ${K_1}$ -> ${K_2}$ 로 가는 경우의 수 + ${K_3}$ -> ${K_4}$로 가는 경우의 수로 정의가 된다. 

 

초기 2*2행렬이 의미하는 바는 ${K_1}$ -> ${K_2}$ 로 가는 경우의 수이고, 이 같은 경우 1분 내에 갈 수 있는 모든 경우의 수를 의미한다.

 

이를 제곱한 새로운 행렬의 원소는 ${K_1}$ -> ${K_2}$ + ${K_3}$ -> ${K_4}$ 가 되므로 2분 내에 갈 수 있는 모든 경우의 수를 의미한다. (  ${K_2 \neq K_3}$ 인 경우는 없다. ) 

 

이를 일반화 시킨다면, 초기 연결 상태를 표현한 인접행렬을 D제곱한다면 D분 내에 갈 수 있는 모든 경우의 수를 표현 할 수 있고

이를 log(N)의 시간이 걸리는 거듭제곱 알고리즘을 통해 ${8^3}$${log(D)}$시간에 정답을 도출 할 수 있다.

참고

https://blog.naver.com/PostView.naver?blogId=gt7461&logNo=110151975370&redirect=Dlog&widgetTypeCall=true&topReferer=https%3A%2F%2Fstack07142.tistory.com%2F119&directAccess=false 

인접행렬과 인접행렬의 거듭제곱

소스 코드

#define ll long long
#define MOD 1000000007LL
#include <bits/stdc++.h>
using namespace std;
ll D;
const vector<vector<ll>> v = {
        {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}
};
vector<vector<ll>> multiply(const vector<vector<ll>>& M1, const vector<vector<ll>>& M2){
    vector<vector<ll>> ret(8, vector<ll>(8));
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            ll elem = 0;
            for(int k=0; k<8; k++){
                elem += (M1[i][k] * M2[k][j]);
                elem %= MOD;
            }
            ret[i][j] = elem % MOD;
        }
    }
    return ret;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> D;

    // D제곱 한 것의 1행 1열의 결과 P->P로 D만큼의 변을 거쳐서 갈 때, 나오는 경우의 수
    vector<vector<ll>> ans(8, vector<ll>(8));
    for(int i=0; i<8; i++){
        ans[i][i] = 1;
    }
    vector<vector<ll>> factor = v;
    while(D){
        if( D & 1 ){
            ans = multiply(ans, factor);
            D -= 1;
        }
        factor = multiply(factor, factor);
        D /= 2;
    }
    cout << ans[0][0] << '\n';
    return 0;
}