[BOJ 20951, C++] 유아와 곰두리차

https://www.acmicpc.net/problem/20951

20951번: 유아와 곰두리차

 

풀이

그래프 문제이니까 바로 그래프 알고리즘을 생각해볼 수 있지만, 문제를 읽다보면 같은 경로를 여러번 지나칠 수 있기 때문에 그래프 알고리즘이 아닌 다른 알고리즘을 생각해볼 수 있습니다.

 

모듈러 연산을 보아하니 DP 또는 그리디부터 추론할 수 있는데, 그리디는 어려우니 DP부터 생각해보면 dp[N][8]로 충분히 만들 수 있고, 1-3-2, 2-3-1 같이 길이가 2일 때 정점 3에서 겹치면 dp[3][2]값을 써먹을 수 있기 때문에 메모이제이션도 사용할 수 있고, 점화식도 쉽게 구할 수 있습니다.

 

그래서 현재 정점의 위치와 현재까지 방문한 길이를 파라미터로 가지고 있는 함수 go(x, len)을 만들어서 dp[x][len] = (dp[x][len] + go(nx, len+1)) % MOD를 해주면 됩니다.

 

 

코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
using ll = long long;
 
const int N = 1e5 + 1, MOD = 1e9 + 7;
int n, m, u, v;
ll dp[N][8];
vector<int> adj[N];
 
ll go(int x, int len) {
    if (len > 7) return 1;
    ll& ret = dp[x][len];
    if (ret != -1) return ret;
 
    ret = 0;
    for (auto nx: adj[x]) {
        ret = (ret + go(nx, len + 1)) % MOD;
    }
 
    return ret;
}
 
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
 
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        adj[--u].push_back(--v);
        adj[v].push_back(u);
    }
 
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans = (ans + go(i, 1)) % MOD;
    }
    cout << ans << endl;
}