[Python] 백준 14289번: 본대 산책3

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

14289번: 본대 산책 3

 

import sys

input = sys.stdin.readline
MOD = 1000000007


def multiply_matrix(matrix1, matrix2):
    return [[sum(matrix1[i][k]*matrix2[k][j] % MOD for k in range(n)) % MOD
             for j in range(n)] for i in range(n)]


def solution(D):
    # DP 초기화
    dp1 = [[0]*n for _ in range(n)]
    for k, v in graph.items():
        for adj in v:
            dp1[k][adj] = 1

    dp2 = [[0]*n for _ in range(n)]
    for i in range(n):
        dp2[i][i] = 1

    # 행렬 제곱
    while D > 0:
        if D % 2 == 1:
            dp2 = multiply_matrix(dp1, dp2)
            D -= 1
        dp1 = multiply_matrix(dp1, dp1)
        D //= 2

    return dp2[0][0]


if __name__ == '__main__':
    n, m = map(int, input().split())

    graph = {i: [] for i in range(n)}
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    D = int(input())

    print(solution(D))

 

인접행렬의 곱을 통한 경우의 수 구하기를 조금 응용한 문제이다. 아래 링크를 참고하자.

https://rccode.tistory.com/entry/Python-%EC%9D%B8%EC%A0%91%ED%96%89%EB%A0%AC%EC%9D%98-%EC%A0%9C%EA%B3%B1%EB%B0%B1%EC%A4%80-12850%EB%B2%88-%EB%B3%B8%EB%8C%80-%EC%82%B0%EC%B1%85-2

[Python] 인접행렬의 제곱(백준 12850번: 본대 산책 2)

 

12850번에서 초기값이 고정되어있지 않다는 점이 다른 점이다. 이에 대해서, dp1(1번 이동했을 때의 경우의 수)를 초기화시켜주는 점 말고는 변함이 없다.