BOJ 1533 길의 개수

시작점 S에서 끝점 E까지 정확하게 시간 T만에 가는 경로의 개수를 구하는 문제이다.

백준님의 풀이를 정리하기 전에, 먼저 알아야할 것이 있다.
이 문제의 입력처럼 인접한 정점 사이의 길의 정보를 나타낸 인접행렬을 A라고 하면 A[i][j]가 나타내는 정보는 i에서 j까지 도로 하나를 이용할 때(즉, 다른 정점을 거치지 않을 때) 거리는 시간인데, A[i][j]를 도로 하나를 이용할 때의 i에서 j까지의 경로의 개수라고 놓고 생각해보자. 그럼 A의 제곱은 어떤 의미를 지닐까? 행렬의 곱의 과정을 살펴보고, 결과를 보면 A^2[i][j]는 도로 두 개를 이용할 때의 i에서 j까지의 경로의 개수라는 것을 알 수 있고, 결국 A^n[i][j]는 도로 n개를 이용할 때의 i에서 j까지의 경로의 개수라는 것을 알 수 있다.

근데 이 것이 이 문제에서 어떻게 활용될 수 있을까?
i에서 j까지 시간 T만에 간다는 것은, 걸리는 시간이 1인 길을 T개 이용한다는 것과 같다. 바로 이 아이디어가 이 문제를 푸는 핵심이다. 이 아이디어를 활용하기 위해서 모든 길을 시간으로 나눈다. 문제의 조건에 보면 입력으로 주어지는 길 하나당 이동 시간이 최대 5이므로 최대 5등분까지 하면 되고, 그렇게 시간으로 나눠서 도로 위에 시간 1당 정점을 하나씩 추가하면 시간이 1인 길들로 도로를 재구성할 수 있다.

이제 위의 아이디어를 이용하면 T만큼 행렬의 곱셈을 통해서 S부터 E까지의 도로의 개수를 구할 수 있다. 그런데 여기서 또 걸리는 것이 하나 있는데 바로 T가 무려 10억이라는 것이다. 그럼 10억번을 곱해야하나?? 곱셈은 이진수의 원리를 이용하면 logN만에 할 수 있다.

예를 들면,  A^27 = A^(11011) = A^(1+2+8+16) = A^1 + A^2 + A^8 + A^16 이렇게 A의 (2의 n제곱수)의 제곱의 합으로 이루어지고 A^2=A*A, A^4=A^2 * A^2, A^8=A^4*A^4 .... 이므로 각각 O(1)만에 구할 수 있고, 총 O(logN)만에 구할 수 있다.
관련 문제 : BOJ 13171 A (제 4회 kriiicon P1번) - 이 문제에 자세한 설명이 나와있다.

그리고 백준님의 코드에서 행렬의 곱셈을 구현할 때, operator * ...부분을 따로 함수로 만들고 *만해도 저절로 행렬의 곱셈이 되도록 되어있는데 이렇게 하는 것을 연산자 오버로딩(operator overloading)이라고 하는 것 같다.
참고 : operator overloading 설명 블로그


출처 ; 백준님 알고리즘 문제풀이 강의, 백준님 강의 자료