[백준 파이썬] 12850 본대 산책2

백준 12850

[행]에서 출발해 [열]로 가는 방법을 그래프로 나타낸 후 푼다

예시로 경로가 0에서 1, 1에서 0밖에 없다고 하면

두번 이동한다면

따라서 같은 시작 노드에서 도착 노드까지 가는 방법의 수는 이동하는 횟수만큼 행렬을 곱하고 그에 해당하는 행과 열의 값을 선택하면 된다.

def matrix_mul(A, B):
    ans = [[0 for _ in range(len(A))] for _ in range(len(B[0]))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            temp = 0
            for k in range(len(B)):
                temp += A[i][k] * B[k][j]
            ans[i][j] = temp % 1_000_000_007
    return ans

def divide_conquer(A, n):
    if n == 1:
        return A

    else:
        x = divide_conquer(A, n//2)
        if n %2 == 0:
            return matrix_mul(x, x)
        else:
            return matrix_mul(A, matrix_mul(x, x))
        
edges = [
    [0, 1],
    [0, 2],
    [1, 2],
    [1, 3],
    [2, 3],
    [2, 4],
    [3, 4],
    [3, 5],
    [4, 5],
    [4, 7],
    [5, 6],
    [6, 7],
]
graph = [[0 for _ in range(8)] for _ in range(8)]
for i, j in edges:
    graph[i][j] = graph[j][i] = 1

N = int(input())
print(divide_conquer(graph, N)[0][0])