[백준] 12850 - 본대 산책 2 (G1)

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

12850번: 본대 산책2

처음엔 그림만 보고 그래프 문제를 예상했는데,

문제를 읽어보니 경우의 수를 세라길래 DP로 예상해서 DP 점화식을 세웠다.

근데 dp테이블을 일일히 채우고 있다가는 저 10억이라는 입력데이터를 감당하지 못하겠다는 생각이 들었다.

 

그래서 결국 알고리즘 분류를 봤다..

그런데 띠용.. '분할정복을 이용한 거듭제곱' 문제라고 소개가 되어있었다.

 

다행히 이걸 보고 전에 풀었던 피보나치 문제가 스쳐지나갔다.

행렬 거듭제곱을 이용해서 피보나치 수열을 빠르게 구하는 문제였다.

 

그런데 부끄럽게도 그 문제를 풀 당시에는 피보나치 수열을 구하는 행렬식을 세우는 원리를 이해하지 못하고

"와 미쳤다.. 어떻게 이런걸 떠올리지?" 하면서 그냥 정답코드를 보고 행렬식만 베껴 풀었었다.

 

이번에는 그 행렬식을 세우는 원리를 이해하고 싶어 인터넷을 검색해 공부를 하고 풀어봤다.

내가 봤던 글은 아래 글이었다.

https://driip.me/00556a4c-0782-4c5b-a86a-8e27e5f4ac1b

행렬 거듭제곱을 이용한 선형 점화식의 DP 풀기

이 글을 보고 나서 행렬 식을 세우는 원리를 이해할 수 있었다.

---

이제 이 게시글을 보고 이해한 원리를 이 문제에 적용해보았다.

DP식을 세우는 방법을 떠올리는 건 많이 어렵지 않았다.

 

나는 주어진 그래프에 아래와 같이 번호를 매겼다.

0번이 정보과학대이다.

그리고 나는 아래와 같이 식을 생각했다.

 

시간이 n 분 남았을 때 i번 노드에서 0번 노드로 돌아가는 경우의 수

 

기본적으로 시간이 0분남았을 때 0번 노드로 돌아가야 하므로

시간이 0분 남았을 때 0번 노드에서 0번 노드로 돌아가는 경우의 수를 1로 정의하고

0분 남았을 때 나머지 노드에서 0번 노드로 돌아가는 경우의 수를 0으로 설정한다.

 

그리고 시간이 n 분 남았을 때 i 번 노드에서 0번 노드로 돌아가는 경우의 수를 Ain 라고 하면

인접한 노드에 따라 아래와 같이 점화식이 세워진다.

 

0번 노드는 1, 2번 노드와 인접해 있다.

0번 노드에서 0번 노드로 n 분 만에 돌아가는 경우의 수는

1번 노드와 2번 노드에서 0번 노드로 n-1 분 만에 돌아가는 경우의 수와 같으므로

 

A0n = A1n-1 + A2n-1

 

와 같이 식을 세울 수 있다.

 

현재 위치에서 인접한 노드들로 이동한다고 보고,

각 인접노드들에서  n-1분 만에 0번 노드로 돌아가는 식을 세우는 것이다.

 

이걸 행렬 식으로 표현하면 아래와 같이 된다.

이제 이 과정을 매 분 반복하면 된다.

즉 이 행렬식을 계속 중첩해서 곱해 나가면 된다

 

이때 [A00 ~ A70] = [1 0 0 ... 0 0] 인 것을 감안하면 이 문제를 푸는 정답 식은

N 분만에 정보과학대로 돌아오는 경우의 수는

(작성한 행렬식)^n * [1 0 0 ... 0 0]

의 값에서 A0N 의 값이다.

 

이제 이 문제는 행렬제곱을 빠르게 계산하는 문제로 바뀌었다.

행렬의 거듭제곱을 분할정복을 이용해 빠르게 계산해내면 된다.

 

글로 설명하려니까 뭔가 설명이 잘 안되는 것 같다.

 

아래는 이를 코드로 작성한 것이다.

나는 파이썬으로 풀 때 행렬을 인자에 넘겨주는 과정에서 깊은 복사가 일어나도록

리스트를 튜플로 바꿔서 넘겨주도록 했다.

 

MOD = 1000000007

def mul(m1, m2): # 두 행렬 m1 m2 곱해서 그 결과 행렬 리턴
  ret = [[0 for _ in range(len(m2[0]))] for _ in range(len(m1))]
  
  for i in range(len(m1)):
    for j in range(len(m2[0])):
      for k in range(len(m1[0])):
        ret[i][j] += m1[i][k]*m2[k][j]
        ret[i][j] %= MOD
    ret[i] = tuple(ret[i])
    
  ret = tuple(ret)
  return ret


def pow(matrix, n):
  if n == 1:
    return matrix
  temp = pow(matrix, n//2)
  ret = mul(temp, temp)
  if n%2 == 1:
    ret = mul(ret, matrix)

  return ret
    


n = int(input())
matrix = (
  (0, 1, 1, 0, 0, 0, 0, 0),
  (1, 0, 1, 1, 0, 0, 0, 0),
  (1, 1, 0, 1, 1, 0, 0, 0),
  (0, 1, 1, 0, 1, 1, 0, 0),
  (0, 0, 1, 1, 0, 1, 1, 0),
  (0, 0, 0, 1, 1, 0, 0, 1),
  (0, 0, 0, 0, 1, 0, 0, 1),
  (0, 0, 0, 0, 0, 1, 1, 0)
)

first = ((1,), (0,), (0,), (0,), (0,), (0,), (0,), (0,))

result = mul(pow(matrix, n), first)
answer = result[0][0]
print(answer)

이 문제를 푸는데 생각보다 시간이 오래걸렸는데,

그 이유는 행렬곱과 행렬 거듭제곱 구현을 너무 오랜만에 해봐서...ㅋㅋㅋㅋ

그 부분을 구현할 때 시간이 오래 걸렸다..ㅎ

 

진짜 오랜만에 (거의 3달..?) 백준 풀었는데, 개발한다고 알고리즘을 너무 놓지 않도록 해야겠다.