백준온라인 1533번 [길의 개수] [C++]

www.acmicpc.net/problem/1533

1533번: 길의 개수

---

문제 요약

1. 입력 n(행렬의 사이즈) , T(시간) , S(시작점), E(끝 지점)과 행렬이 다음 입력으로 주어진다

2. 행렬의 정의가 matrix [i][j]가 0보다 같거나 크고 5 이하인 게 보장되고 그럴 경우 i에서 j로 가는데 걸린 시간을 표현

3.T시간 동안 S에서 E까지 갈 수 있는 경로의 가짓수를 1,000,003으로 나눈 나머지로 출력

---

나의 풀이

처음 이문제를 보자마자 

www.acmicpc.net/problem/12850

12850번: 본대 산책2

이 문제가 떠올랐다. 

위문제는 행렬이 "인접 행렬"(이동 1회에 해당하여 i에서 j로 갈 수 있는지 없는지 true false 값들로 이루어진 행렬)

로 주어져있다

그래서 "경로 찾기" 문제도 비슷한 문제라고 생각을 했지만

주어진 행렬의 정의가 인접 행렬이 아니기에 너무 어려워 구글링을 하여 문제를 풀었다

 

경로 찾기 문제에서의 중요한 발상은

 

1초가 넘게 걸리는 경로에 대해서 새로 정의한 경로를 우회하여 거쳐가도록 해주는 것이다

 

예를 들어.

	1	2	3
1	0	1	2
2	2	0	1
3	1	2	0

 

다음과 같이 행렬이 주어질 경우

i, j 가 (1,2) (2,3), (3,1) 같이 1로 되어있는 경우 중

(1,2)는

(1번 정점의 0초)에서  (2번 정점의 0초)까지 한 번에 갈 수 있다고 이해해보자

 

 

(1,3), (1,2), (3,2)와 같이 2 이상인 경로들 중

(1,3)는

(1번 정점의 0초)에서 (1번 정점의 1초)로 한번 가고

(1번 정점의 1초)에서 (3번 정점의 0초)로 한 번에 간다고 표시해두는 방식이다

 

즉 모든 경로의 값이 5 이하인 게 보장이 되므로 

모든 정점에 대해서 해당 값만큼 맴돌아주다가 마지막에 다른 정점으로 가는 식으로 행렬을 재구성해주면 되는 것이다

 

이 문제는 N(정점의 개수)이 최대로 10이므로

 

각 정점마다 5초까지 있을 수 있으므로  

\(5N \times 5N\) 만큼의 행렬을 준비해주고 문제에서 준 행렬을 재구성한 다음 행렬의 거듭제곱 성질을 이용하여 계산을 해주면 된다.

---

코드