백준 20951번 파이썬 문제풀이(유아와 곰두리차) - DP(탑다운)

---

이 문제의 핵심은 여러 경로들을 지나간 횟수와 그 때 현재의 노드를 기준으로 dp[현재의 노드][지나간 횟수]를 저장하는 것이다. 3을 기준으로 본다면 1 -> 2 -> 3 -> 4 ... 2 -> 1 -> 4 -> 3 -> 5 ... 4 -> 2 -> 3 -> 6.... 과 같이 3이 3번째인 수많은 경로가 나온다고 할 때 3번째에 3의 정점을 지나가는 경우의 수는 미리 구해놓으면 다음번에 지나갈 때 굳이 또 검사를 안해도 된다는 것이다. 또한 10^9 + 7을 계산할 때마다 나누어서 저장해주어야 한다는 점 또한 잘 체크해야 한다.

import sys


def dfs(cur, cnt):

    if cnt > 7:
        return 1

    if dp[cur][cnt] != -1:
        return dp[cur][cnt]

    dp[cur][cnt] = 0
    for nxt in graph[cur]:
        dp[cur][cnt] = (dp[cur][cnt] + dfs(nxt, cnt + 1)) % MOD

    return dp[cur][cnt]


ans = 0
MOD = 1e9 + 7
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
dp = [[-1] * 8 for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, N + 1):
    print(dfs(i, 1))
    ans = (ans + dfs(i, 1)) % MOD

print(f'{ans:.0f}')