글 목차
728x90
이 그래프를 인접행렬로 나타내면 다음과 같다.
예를 들어 A -> B로 가는 방법은 1개이다.
그렇다면 A에서 두번 거쳐 B로 가는 방법은 몇개일까?
(A-A-A), (A-B-A), (A-C-A)로 나타낼 수 있다. 신기하게도 이 인접행렬을 제곱하면 된다. (계산해보면 같다는걸 알 수 있음)
그럼 변 세 개를 거치는건? 인접행렬을 세제곱하면 된다!
https://www.acmicpc.net/problem/12850
12850번: 본대 산책2
가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.
www.acmicpc.net
이문제를 풀어보면 알 수 있따.
728x90