[백준] 17401 - 일하는 세포 (Python)

혈관 지도를 행렬로 표현해보자. 이때, 적혈구는 모든 거점에서 출발하므로 초기 상태는 길이가 $n$인 단위행렬과 같다.

$\begin{pmatrix}1&0&0\\0&1&0\\0&0&1 \end{pmatrix}$ $\times$ $\begin{pmatrix}0&1&0\\0&1&1\\1&0&1 \end{pmatrix}$

위 행렬식의 결과는 $1$초까지 적혈구가 움직일 수 있는 경우의 수와 그 위치를 표현할 것이다.

매번 변하는 혈관 지도를 계속해서 곱해 준다면 답을 구할 수 있다.
하지만 $d$가 매우 큰 값일 가능성이 있다. 이런 경우에는 혈관 지도가 $t$초를 주기로 반복된다는 것을 이용해야 한다.

$q = d/t,\,r = d\;mod\;t$라 하자.
$t$ 초까지의 혈관 지도를 곱하면 $t$초를 한번에 이동할 수 있는 행렬을 구할 수 있다.
이 결과를 $T$라 하고 중간의 $r$초에서 결과를 $R$로 놓자.
단위 행렬을 $I$라 할 때 $d$초 동안 이동한 결과를 표현하는 최종 행렬은 아래와 같다.

import sys, copy
input = sys.stdin.readline

# 두 행렬을 곱해서 A에 결과를 저장
def mult_matrix(A, B):
    global n
    global temp
    for x in range(n):
        for y in range(n):
            temp[x][y] = 0
    for x in range(n):
        for y in range(n):
            for k in range(n):
                temp[x][y] += A[x][k]*B[k][y]
    for x in range(n):
        for y in range(n):
            A[x][y] = temp[x][y] % 1_000_000_007

# 거듭제곱의 결과를 res에 저장
def power_matrix(res, p):
	# T
    global result
    if p == 1:
        return
    power_matrix(res, p//2)
    mult_matrix(res, res)
    if p % 2:
        mult_matrix(res, result)
    return

def print_arr(arr):
    for row in arr:
        print(*row)
        
def main():
    global n
    t, n, d = map(int, input().rstrip().split())
    # 시작 상태를 저장하는 단위 배열 I
    init_mat = [[1 if j==i else 0 for j in range(n)] for i in range(n)]
    if d == 0:
        print_arr(init_mat)
        return
    
    # 혈관 지도
    graph = [[[0]*(n) for _ in range(n)] for _ in range(t)]
    for i in range(t):
        m = int(input())
        for _ in range(m):
            a, b, c = map(int, input().rstrip().split())
            graph[i][a-1][b-1] = c
            
    global temp
    temp = [[0]*(n) for _ in range(n)]
    r = d % t
    q = d // t
    # 나머지 행렬
    r_mat = 0
    
    global result
    result = copy.deepcopy(graph[0])
    # t초까지 혈관 지도를 모두 곱해줌
    for i in range(1, t):
    	# r초인 시점에 이동 결과
        # r == 0 이면 저장되지 않음
        if i == r:
            r_mat = copy.deepcopy(result)
            if d <= t:
                mult_matrix(init_mat, r_mat)
                print_arr(init_mat)
                return
        mult_matrix(result, graph[i%t])
        
    res = copy.deepcopy(result)
    if q > 1:
        power_matrix(res, q)
    mult_matrix(init_mat, res)
    if r_mat:
        mult_matrix(init_mat, r_mat)
        
    print_arr(init_mat)
    return

main()