[Python] 12850번 본대 산책2

 

 

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

---

 

23/03/21

 

 

예전에 이 문제에 대한 풀이 글을 작성한 것 같았는데, 지금 검색해보니 작성하지 않아서 오랜만에 작성하려고 한다.

 

그래프를 인접 행렬로 나타낼 수 있는지에 대한 지식과, 그 행렬을 거듭제곱하면 경로의 개수가 나온다는 지식을 요구하는 문제다. 

---

 

문제 접근 방식:

 

 

본대 산책1이 있고 본대 산책2가 있는데, 둘은 제한만 다른 문제다.

 

본대 산책2는 본대 산책1에 분할 정복을 이용한 거듭제곱 태그가 들어가서 난이도가 더 뛰어버렸다. (사실 그 정도로 어려운가 싶지만, 그렇다고 하자.)

 

문제에서 주어진 그래프를 인접 행렬의 형태로 바꿔보자.

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, 0, 1],
          [0, 0, 0, 1, 1, 0, 1, 0],
          [0, 0, 0, 0, 0, 1, 0, 1],
          [0, 0, 0, 0, 1, 0, 1, 0]]

 

결론은 저 행렬을 $D$번 거듭제곱하여, matrix[0][0]의 값을 구하면 끝이다.

 

그 이유는, 인접 행렬을 $N$번 거듭제곱한 행렬을 $M$이라고 할 때, $M[i][j]$는 $i$번 노드에서 출발 하여 $N$번 움직여서 $j$번 노드에 도착하는 경로의 개수이기 때문이다.

 

이에 대해 잘 알지 못하는 사람은 이 글을 보면, 엥 왜 그러지? 라고 생각할 것이다.

여기서 설명하기에는 조금 길어서, 아래 나무위키 문서를 참고해보자. 수학적 귀납법으로 이를 증명한다.

https://namu.wiki/w/%EC%9D%B8%EC%A0%91%ED%96%89%EB%A0%AC#s-4

인접행렬

증명이 궁금한 것이 아니라 직관적으로 알아보고 싶다면, 아래 블로그 글을 참고해보자.

https://blog.naver.com/gt7461/110151975370

인접행렬과 인접행렬의 거듭제곱

 

$0$번 노드를 정보과학관으로 삼아서 연결 관계를 표시한 것이기 때문에, matrix[0][0]의 값을 구한 것이다.

 

이때, 행렬의 곱셈은 행렬의 크기가 $N$이라고 하면, $\mathcal{O}(N^3)$의 시간 복잡도가 소요된다.

주어지는 $D$의 제한은 최대 10억이므로, 당연히 나이브하게 10억번 곱셈을 하면, 몇천억번 계산을 해야한다.

 

따라서 곱셈의 횟수를 줄이기 위해 행렬 곱셈을 할 때, 분할 정복을 사용할 수 있다.

그러면 시간 복잡도는 로그로 줄어들게 되고, 충분히 시간 제한 안에 행렬 곱셈을 진행할 수 있다.

 

중간에 계속 모듈로 연산을 취해주는 것을 잊지 말자.

 

똑같은 방법으로 본대 산책 3을 해결할 수 있다. 다만 본대 산책 3은 그래프의 연결 관계를 입력 받은 대로 인접 행렬을 직접 구성해야한다는 점이 조금 다르다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 12850번 본대 산책2
# 수학, 분할정복을 이용한 거듭제곱
def matrixmult(A, B, mod, k):
    K = [[0 for _ in range(k)] for _ in range(k)]
    for i in range(k):
        for j in range(k):
            ele = 0
            for m in range(k):
                ele += (A[i][m]*B[m][j])%mod
            K[i][j] = ele%mod
    return K
def multiply(A, n, mod, k):  # 행렬, 몇제곱할건지, 나머지, 행렬크기
    if n == 1:
        return A
    temp = multiply(A, n//2, mod, k)
    if n%2 == 0:
        return matrixmult(temp, temp, mod, k)
    else:
        return matrixmult(A, matrixmult(temp, temp, mod, k), mod, k)
def fib(n):
    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, 0, 1],
              [0, 0, 0, 1, 1, 0, 1, 0],
              [0, 0, 0, 0, 0, 1, 0, 1],
              [0, 0, 0, 0, 1, 0, 1, 0]]
    if n == 1:
        return 0
    else:
        K = multiply(matrix, n, 1000000007, 8)
        return K[0][0]
print(fib(int(input())))