[Python] 14289 - 본대 산책 3 (골드1)

1. 문제 설명

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

14289번: 본대 산책 3

아이디어를 떠올리지 못 해서 구글링하긴 했었지만,

이 문제를 풀 때가 전역한지 얼마 안 된 때라 행렬의 개념을 다 잊어먹어서 더 고생했었다.

 

---

2. 아이디어

행렬을 이해해야 한다. 그러면 dp와 분할 정복으로 풀이할 수 있다.

(다르게 풀이한 사람이 있을까 싶어 찾아봤는데 못 찾겠다.)

입력 정보를 받은 행렬과 단위 행렬을 각각 하나씩 만든다.

 

	a1	a2
a1	a11	a12
a2	a21	a22

여기서 행렬은 이동 횟수라는 개념으로 쓸 수 있다.

위의 표와 같은 어떤 정점과 간선 정보를 담은 행렬 A를 받았을 때, A를 제곱하면 다음과 같다.

 

a11a11	a12a21
a21a12	a22a22

'이동 횟수'이기에 a12a21은 1->2->1로 이동한 경로의 경우의 수를 의미한다.

처음의 행렬과 지금의 행렬을 곱하면 3번 이동, 현재 행렬을 제곱하면 4번 이동한 셈이다.

 

즉, 행렬곱(Matrix Multiple)은 이동 횟수의 홀, 짝 여부를 고려하여 N번 제곱해주면

N번 이동한 횟수를 구할 수 있게 되는 것이다.

 

---

3. 코드

import sys

input = sys.stdin.readline
MOD = 1000000007

def matrix_multiple(matrix1, matrix2): # 행렬 곱
    tmp = [[0]*(n) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                tmp[i][j] += matrix1[i][k] * matrix2[k][j]
                tmp[i][j] %= MOD
    return tmp

def work(graph:dict, d): 
    cache1 = [[0]*(n) for _ in range(n)] 
    cache2 = [[0]*(n) for _ in range(n)] 
    
    for key, value in graph.items(): # [출발 노드][도착 노드] = 경우의 수
        for idx in value:
            cache1[key][idx] = 1
    for i in range(n):
        cache2[i][i] = 1 # 단위 행렬 & 각 건물에서 제자리 위치인 경우

    while d > 0: # 분할 정복 : 행렬을 이동횟수만큼 거듭제곱했을 때 [1][1]의 경우의 수가 답
        if d % 2 == 1: # 이동횟수가 홀수인 경우에 진행된 만큼 cache2를 갱신시키고 이동횟수 1 감소.
            cache2 = matrix_multiple(cache1, cache2) 
            d -= 1
        cache1 = matrix_multiple(cache1, cache1) # cache1로 계속 이동
        d //= 2 # 행렬을 제곱함으로써 이동횟수는 반감된다.
    return cache2[0][0] 

def solution():
    graph = {i : [] for i in range(n)} # 노드 간선 연결
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    d = int(input())
    print(work(graph, d))
    
if __name__ == '__main__':
    n, m = map(int, input().split())
    solution()