[백준] 12849번 본대 산책 (C++)

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

 

 

이 문제는 그래프를 만들어 D 시간이 주어졌을때 여러 경로를 이동하여 다시 돌아오는 경우의 수를 출력하는 문제이다.

 

따라서 그래프 간선관계를 만들어 dp배열을 사용하여 경우의수를 탐색해야 한다.

 

 

dp[시간][노드] = 경우의수

로 2차원 배열로 만들어 시간을 1초씩 늘린다음 노드를 확장시켜 경우의 수를 계속 누적시켜 더했다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int D;
vector<vector<int>> v(8);
vector<pii> tmp = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4},
                   {3, 4}, {3, 5}, {4, 5}, {5, 6}, {6, 7}, {4, 7}};
ll dp[100001][8];

void solve() {
    for(auto it : tmp) {
        int a = it.first;
        int b = it.second;

        v[a].push_back(b);
        v[b].push_back(a);
    }

    dp[0][0] = 1;

    for(int i = 1; i <= 100000; i++) {			// 시간
        for(int j = 0; j < 8; j++) {			// 노드	
            for(auto it : v[j]) {				// 탐색하려는 노드에 연결된 노드들 확장
                dp[i][it] += dp[i-1][j];
                dp[i][it] %= 1000000007;
            }
        }
    }

    cout << dp[D][0];
}

void input() {
    cin >> D;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

문제를 처음 봤는데 되게 신기했던 문제였다 그래프를 확장시키며 dp 배열을 채우는게

좀 새롭게 접한 방법이였던 것 같다.