[BOJ 12850 // C++] 본대 산책 2

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14470번 문제인 전자레인지이다.

 

문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/12850

12850번: 본대 산책2

산책시간이 더 적게 제약이 걸린 다음 문제도 있다.

www.acmicpc.net/problem/12849

 

이 문제는 주어진 캠퍼스지도를 그래프로 생각하고 adjacency matrix(인접행렬)을 만들어 그 성질을 이용하는 것으로 풀 수 있다. adjacency matrix를 n제곱한 행렬의 i행 j열 성분은 node i에서 j로 가는 길이 n짜리 경로의 개수이다.

 

일반적으로 adjacency matrix는 그래프를 표현할 때 없는 edge에 대한 정보까지 0이라는 숫자로 기록하기 때문에 많은 문제에서 효율적이지 못한 자료 저장방법이지만, node의 수가 충분히 적을 때 node i에서 j로 가는 주어진 길이의 경로의 수를 구하는 데에는 쓰기 매우 좋다. 행렬은 binary exponentiation을 통해 빠르게 거듭제곱을 구할 수 있기 때문이다.

 

따라서 이 문제를 푸는 과정은 다음과 같다.

 

1) 지도를 그래프로 보고 adjacency matrix를 만든다.

글쓴이는 문제의 지도에서 정보과학관을 0, 전산관을 1, 미래관을 2, 신양관을 3, 한경직기념관을 4, 진리관을 5, 형남공학관을 6, 학생회관을 7로 잡고 adjacency matrix를 만들었다.

 

2) binary exponentiation으로 adjacency matrix의 D(문제에서 주어진 산책시간) 제곱을 구한다.

 

3) 구하는 산책경로는 정보과학관에서 정보과학관으로 가는 경로이므로 거듭제곱한 행렬의 0행0열 성분을 답으로 출력한다.

 

다음은 제출한 소스코드이다.

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

// mat: adjacency matrix, ans: identity matrix, tmp: 계산과정 중간저장용
long long mat[8][8] = { {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,1,0},{0,0,0,1,1,0,0,1},{0,0,0,0,1,0,0,1},{0,0,0,0,0,1,1,0} };
long long ans[8][8] = { {1,0,0,0,0,0,0,0},{0,1,0,0,0,0,0,0},{0,0,1,0,0,0,0,0},{0,0,0,1,0,0,0,0},{0,0,0,0,1,0,0,0},{0,0,0,0,0,1,0,0},{0,0,0,0,0,0,1,0},{0,0,0,0,0,0,0,1} };
long long tmp[8][8];
int main()
{
    int D;
    cin >> D;
    while (D > 0) { // binary exponentiation
        if (D & 1) {
            for (int i = 0;i < 8; i++) {
                for (int j = 0;j < 8;j++) {
                    for (int k = 0;k < 8;k++) {
                        tmp[i][j] += mat[i][k] * ans[k][j];
                    }
                }
            }
            for (int i = 0;i < 8; i++) {
                for (int j = 0;j < 8;j++) {
                    ans[i][j] = tmp[i][j]%1000000007;
                    tmp[i][j] = 0;
                }
            }
        }
        for (int i = 0;i < 8; i++) {
            for (int j = 0;j < 8;j++) {
                for (int k = 0;k < 8;k++) {
                    tmp[i][j] += mat[i][k] * mat[k][j];
                }
            }
        }
        for (int i = 0;i < 8; i++) {
            for (int j = 0;j < 8;j++) {
                mat[i][j] = tmp[i][j] % 1000000007;
                tmp[i][j] = 0;
            }
        }
        D >>= 1;
    }
    cout << ans[0][0];

    return 0;
}