[백준 12850번] 본대 산책2 (Python3)

import sys
input = sys.stdin.readline
mod = 1000000007

D = int(input())

graph = [[0]*8 for i in range(8)]

graph[0][1] = graph[0][2] = 1
graph[1][0] = graph[1][2] = graph[1][3] = 1
graph[2][0] = graph[2][1] = graph[2][3] = graph[2][4] = 1
graph[3][1] = graph[3][2] = graph[3][4] = graph[3][5] = 1
graph[4][2] = graph[4][3] = graph[4][5] = graph[4][7] = 1
graph[5][3] = graph[5][4] = graph[5][6] = 1
graph[6][5] = graph[6][7] = 1
graph[7][4] = graph[7][6] = 1

def multiply(A,B):
  result = [[0]*8 for i in range(8)]
  for i in range(8):
    for j in range(8):
      for k in range(8):
        result[i][j] += A[i][k]*B[k][j]
      result[i][j] %= mod
  return result

def cal(A,n):
  if n == 1:
    return A
  cal2 = cal(A,n//2)
  if n%2 == 0:
    return multiply(cal2,cal2)
  else:
    return multiply(multiply(cal2,cal2),A)

result = cal(graph,D)
print(result[0][0])

 

"인접행렬" 이라는 개념에 대해서 모르면 절대 풀 수 없는 문제였다.

놀랍게도 a에서 b로 가는 경우의 수가 곧 인접행렬을 거듭제곱한 행렬의 a행 b열의 값이라고 한다.

 

인접행렬을 거듭제곱해야 한다는 사실만 안다면 분할정복 거듭제곱은 이전에 많이 사용해본 알고리즘이니 떠올리기는 쉽다. 행렬 제곱 문제를 풀듯이 풀어주면 된다.

 

 

오늘의 교훈) 인접행렬의 개념에 대해서 좀 더 공부해보자