# [Gold V] 유아와 곰두리차 [문제 링크](https://www.acmicpc.net/problem/20951) ## 문제 설명 <p>유아는 새해를 맞이하여 V.Nets의 자율 주행 자동차를 구매하였다. 유아는 새 차를 타고 바다로 가서 회를 잔뜩 먹고 올 것이다(유아는 감염병 예방을 위한 정부의 방역지침을 준수한다). 고속도로를 달리던 유아는 놀라 자빠질 수밖에 없었다. V.Nets의 자율 주행 시스템이 형편없었기 때문이다. V.Nets에 큰 배신감을 느낀 유아는 직접 자율 주행 자동차를 설계하기로 결심하였다.</p> <p>곰두리차는 유아가 설계한 자율 주행 자동차이다. 곰두리차는 항상 인접한 정점 중 임의의 정점으로 이동한다. 유아는 출발점에서 도착점까지의 경로가 존재하고 시간이 무한하다면 곰두리차가 언제나 목적지에 도달할 수 있다고 믿고 있다. 유아는 문득 그래프가 주어졌을 때, 곰두리차가 지날 수 있는 경로가 몇 개인지 궁금해졌다.</p> <p>하지만 유아는 이 문제를 풀지 못하였다. 문제의 난이도를 낮추기 위하여 유아는 경로상에서 동일한 정점 또는 간선을 재방문하는 것을 허용하였다.</p> <p>그래프가 주어졌을 때, 곰두리차가 지날 수 있는 경로 중 길이가 7인 경로의 개수를 구하는 프로그램을 작성하시오. 곰두리차는 동일한 정점 또는 간선을 여러 번 지날 수 있다.</p> ## 입력 <p>첫 번째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.</p> <p>이후 M개의 줄에 걸쳐 간선이 연결하는 두 정점 번호 u, v가 주어진다.</p> <p>주어지는 간선은 양방향 간선이며, 모든 입력은 공백으로 구분되어 주어진다.</p> ## 출력 <p>첫 번째 줄에 곰두리차가 지날 수 있는 경로 중 길이가 7인 경로의 개수를 출력한다. 답이 매우 커질 수 있으므로 10⁹ + 7로 나눈 나머지를 출력한다.</p> ## 풀이 모든 정점에 대해 이웃한 모든 정점으로의 이동을 7번 반복하는 문제입니다, ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAX = 100'000; const ll MOD = 1e9+7; ll dp[MAX], nextDp[MAX]; vector<vector<int>> conn(MAX); int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; while(m--) { int u, v; cin >> u >> v; conn[u-1].push_back(v-1); conn[v-1].push_back(u-1); } fill(dp, dp+n, 1); for(int i=0;i<7;i++) { memset(nextDp, 0, sizeof nextDp); for(int cur=0;cur<n;cur++) { for(int next:conn[cur]) { nextDp[next] = (nextDp[next]+dp[cur])%MOD; } } memcpy(dp, nextDp, sizeof dp); } cout << accumulate(dp, dp+n, 0LL)%MOD << '\n'; } ```