백준 #12850 - 본대 산책2

초벌

MOD=10**9+7
bd=[1,0,0,0,0,0,0,0]
for _ in range(int(input())):
    bd=[(bd[1]+bd[2])%MOD,
    (bd[0]+bd[2]+bd[3])%MOD,
    (bd[0]+bd[1]+bd[3]+bd[4])%MOD,
    (bd[1]+bd[2]+bd[4]+bd[5])%MOD,
    (bd[2]+bd[3]+bd[5]+bd[6])%MOD,
    (bd[3]+bd[4]+bd[7])%MOD,
    (bd[4]+bd[7])%MOD,
    (bd[5]+bd[6])%MOD]
    print(bd)
print(bd[0])

실행 안해봐도 TLE일 것 같은 감이 딱 온다... 심지어 티어도 골드1이라서 이렇게 쉽게 풀릴 리 만무함.

---

정석 풀이

아무리 시도해도 안풀려서 태그를 참고했다. 분할정복을 이용한 거듭제곱이라니... 팩토리얼 구할 때 푸는 방식을 사용해야 하나보다. 그렇다면 곱할 때마다 가짓수가 업데이트되는 인접 행렬을 만들어야 된다.

특정 row에서 출발, column에 도착하는 길이 있을 때 1로 두고 없으면 0으로 두면, 다음과 같은 2차원 인접 행렬이 생성된다.

bd=[[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]]

이제 행렬에 특성에 의해 O(logN) 시간복잡도를 가지는 거듭제곱을 사용하여 풀 수 있다. 행렬을 곱한 횟수만큼 이동한 가짓수가 업데이트된다.

시작점은 0번째 index이므로 시작 행렬은 전부 0에 [0][0] 부분만 1로 두면 된다.

이는 각 노드에 대해 정해진 횟수만큼 모든 특정 출발지와 도착지에 대해 이동 가능한 가짓수를 파악하는 방식으로 적합한 풀이방식이다.

인접 행렬을 이렇게 사용할 수 있다는 사실만 알아낸다면, 구현은 어렵지 않게 할 수 있는 문제였다.

<인접 행렬을 사용해서 풀 수 있는 사실을 모르고 풀었을 때 내 모습>

문제

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