6096 : 경로 개수 — DAG에서 s→t 경로 수
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
방향성 비사이클 그래프(DAG)가 주어집니다. 시작 노드 S에서 목표 노드 T까지 도달하는 서로 다른 경로의 개수를 구하는 프로그램을 작성하십시오.
그래프의 크기가 작더라도 경로의 수는 기하급수적으로 많아질 수 있으므로, 단순 DFS 탐색 외에 메모이제이션(Memoization)을 결합해야 시간 초과를 피할 수 있습니다. 결과값은 1,000,000,007로 나눈 나머지를 출력합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 15$ (정수)
• 간선 수 $E$: $0 \le E \le 30$ (정수)
• 결과값은 $1{,}000{,}000{,}007$로 나눈 나머지를 출력합니다.
그래프의 크기가 작더라도 경로의 수는 기하급수적으로 많아질 수 있으므로, 단순 DFS 탐색 외에 메모이제이션(Memoization)을 결합해야 시간 초과를 피할 수 있습니다. 결과값은 1,000,000,007로 나눈 나머지를 출력합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 15$ (정수)
• 간선 수 $E$: $0 \le E \le 30$ (정수)
• 결과값은 $1{,}000{,}000{,}007$로 나눈 나머지를 출력합니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 15)과 간선의 개수 E (0 ≤ E ≤ 30)가 주어집니다.
둘째 줄부터 E개의 줄에 방향 간선 u v (u에서 v로 이동 가능)가 주어집니다.
마지막 줄에는 시작 노드 S와 도착 노드 T가 주어집니다.
둘째 줄부터 E개의 줄에 방향 간선 u v (u에서 v로 이동 가능)가 주어집니다.
마지막 줄에는 시작 노드 S와 도착 노드 T가 주어집니다.
출력 설명
S에서 T까지 도달할 수 있는 모든 경로의 수 modulo 1,000,000,007을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2
1 3
2 4
3 4
1 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
dp[node]를 'node에서 T까지 가는 경로의 수'로 정의하고, DFS 방문 중 이미 계산된 dp 값이 있으면 즉시 반환하도록 메모이제이션을 적용하십시오.