백준 12916 (C++) K-Path

최초 업로드: 2025-08-07 17:46:42

최근 수정 시간: 2025-08-07 17:47:10

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] K-Path

[문제 링크](https://www.acmicpc.net/problem/12916)

## 문제 설명

BOJ 월드에 존재하는 수많은 나라중 하나인 천나라에는 N개의 마을이 있다. 각각의 마을들 사이에는 길이 있을수도 있고 없을수도 있다. 만약 길이 있다면 그 길의 길이는 1로 동일하다.

민호는 천나라의 지도를 만들기 위해 N개의 마을들 사이의 연결성을 인접 행렬로 나타냈다. 그러다 미스테리한 이유로 길이가 K인 경로의 개수가 몇개인지 궁금해졌다.

민호가 작성한 인접행렬이 주어졌을때 길이가 K인 서로 다른 경로의 수가 몇개인지 알아보자.

## 입력

첫 번째 줄에 N, K (1 ≤ N ≤ 100, 1 ≤ K ≤ 109) 이 공백을 구분으로 주어진다.

다음 N개의 줄에 걸쳐 민호가 작성한 인접 행렬이 주어진다. i번 줄의 j번 수가 1이면 i번 마을과 j번 마을의 길이 있다는 얘기고 0이면 길이 존재하지 않는다는 이야기 이다.

## 출력

길이가 K인 경로의 수를 109+7로 나눈 나머지를 출력한다.

## 풀이
#### 행렬 거듭제곱을 이용해 경우의 수를 빠르게 구하였다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const ll MOD = 1e9+7;

int n, k;

vvll square(vvll a, vvll b) {
 vvll ret(n, vll(n));
 for(int i=0;i<n;i++) {
 for(int j=0;j<n;j++) {
 for(int k=0;k<n;k++) {
 ret[i][k] += a[i][j] * b[j][k];
 ret[i][k] %= MOD;
 }
 }
 }
 return ret;
}

ll solve(vvll a) {
 vvll ret(n, vll(n));
 for(int i=0;i<n;i++) ret[i][i]=1;

while(k) {
        if(k & 1) ret = square(a, ret);
        a = square(a, a);
        k>>=1;
    }

ll cnt=0;
 for(int i=0;i<n;i++) {
 for(int j=0;j<n;j++) {
 cnt += ret[i][j];
 }
 }
 return cnt % MOD;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;

vvll a(n, vll(n));
 for(int i=0;i<n;i++) {
 for(int j=0;j<n;j++) {
 cin >> a[i][j];
 }
 }
 cout << solve(a) % MOD;
}
```