[C/C++] 백준 - 20951번 : 유아와 곰두리차

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

20951번: 유아와 곰두리차

문제

유아는 새해를 맞이하여 V.Nets의 자율 주행 자동차를 구매하였다. 유아는 새 차를 타고 바다로 가서 회를 잔뜩 먹고 올 것이다(유아는 감염병 예방을 위한 정부의 방역지침을 준수한다). 고속도로를 달리던 유아는 놀라 자빠질 수밖에 없었다. V.Nets의 자율 주행 시스템이 형편없었기 때문이다. V.Nets에 큰 배신감을 느낀 유아는 직접 자율 주행 자동차를 설계하기로 결심하였다.

곰두리차는 유아가 설계한 자율 주행 자동차이다. 곰두리차는 항상 인접한 정점 중 임의의 정점으로 이동한다. 유아는 출발점에서 도착점까지의 경로가 존재하고 시간이 무한하다면 곰두리차가 언제나 목적지에 도달할 수 있다고 믿고 있다. 유아는 문득 그래프가 주어졌을 때, 곰두리차가 지날 수 있는 경로가 몇 개인지 궁금해졌다.

하지만 유아는 이 문제를 풀지 못하였다. 문제의 난이도를 낮추기 위하여 유아는 경로상에서 동일한 정점 또는 간선을 재방문하는 것을 허용하였다.

그래프가 주어졌을 때, 곰두리차가 지날 수 있는 경로 중 길이가 7인 경로의 개수를 구하는 프로그램을 작성하시오. 곰두리차는 동일한 정점 또는 간선을 여러 번 지날 수 있다.

입력

첫 번째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.

이후 M개의 줄에 걸쳐 간선이 연결하는 두 정점 번호 u, v가 주어진다.

주어지는 간선은 양방향 간선이며, 모든 입력은 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 곰두리차가 지날 수 있는 경로 중 길이가 7인 경로의 개수를 출력한다. 답이 매우 커질 수 있으므로 109 + 7로 나눈 나머지를 출력한다.

---

문제를 잘 읽어보면 문제 속 문제 유형을 알려주는 힌트가 존재한다.

 

"동일한 정점 또는 간선을 재방문 하는 것을 허용하였다." 바로 이 부분이다.

동일 정점 또는 간선의 방문을 허용하면서 모든 경우의 수를 세어주어야 한다. 그렇다면 분명 같은 정점을 같은 길이의 경로로 진행하는 경우가 존재할 것이다. 이런 경우를 새로 세어줄 필요가 있을까? 전혀 없다.

 

즉, 하나의 정점에 같은 길이로 접근하는 경우의 수를 메모이제이션하여 같은 작업을 중복하여 진행하는 일을 없도록 한다. 동적계획법으로 해결하면 되는 문제이다.

 

위에서 말한 문장 그대로 메모이제이션에 적용하면

cache[방문 정점의 번호][현재까지 진행한 경로 길이];

이렇게 해주면 될 것이다.

 

시작점과 도착지점에 대한 설명이 정확히 존재하지 않기 때문에 어느 정점이든 시작점과 도착지점이 될 수 있다. 맞춰주어야 하는 것은 경로의 길이가 7이라는 것밖에 존재하지 않는다.

 

위의 문장들을 전부 코드로 나타내어주면 해결가능하다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define Mod 1000000007
#define endl '\n'

using namespace std;

int N, M;
vector<int> adj[100000 + 1];
long long cache[100000 + 1][7 + 1];

void input(){
    cin >> N >> M;
    for(int i=0;i<M;i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

long long path(int index, int length){
    if(length == 7) return 1;
    long long &ret = cache[index][length];
    if(ret != -1) return ret;
    ret = 0;
    for(auto &next : adj[index]){
        ret += path(next, length+1) % Mod;
    }
    return ret % Mod;
}

long long solution(){
    memset(cache, -1, sizeof(cache));
    long long answer = 0;
    for(int i=1;i<=N;i++){
        answer += path(i, 0) % Mod;
    }
    return answer % Mod;
}

int main(){
    fastio;
    input();
    cout << solution() << endl;

    return 0;
}