[백준/C++] 유아와 곰두리차(No. 20951, 새해 기념)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 잘 생각해보면 이미 이용한 경로를 통해서도 다시 방문을 할 수 있으므로, i번째에 N번째 노드를 방문한 경우를 이용해 i+1번째에 각 노드에 방문할 수 있는 경로가 몇 개인지 계산하면 되는 문제다.

 

이를 잘 생각해보면 이전에 작은 문제의 해결방법을 이용해 다음 문제를 풀 수 있으므로 DP 문제로 생각할 수 있다.

 

fig1

 

그림으로 보면 초록색 부분을 채워 나가면 된다.

 

N개의 노드가 존재하고 i번째에서 N번째 노드를 방문한 경우를 이용해 i+1번째 노드에는 몇 가지 경로가 존재하는지 빠르게 계산할 수 있다.

 

 

 

[아이디어 정리]

1. N * 8 크기의 배열을 만든다.
2. 현재 i번째 이동했을 때, N번째 노드를 방문하는 경우를 배열에 저장한다.
3. 이를 이용해 i+1번째에 N번째 노드로 방문하는 경우의 수가 얼마인지 계산해 나간다.
4. 최종적으로 7번째에 방문할 수 있는 모든 경우의 수를 더해 출력한다.  

 

Code

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>
using namespace std;

const int mod = 1000000000 + 7;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	int a, b;
	vector<vector<int>>v(N+1);
	for (int i = 0; i < M; i++) 
	{
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int ans = 0;
	vector<vector<int>> m(N + 1, vector<int>(8, 0));
	queue<int> q;
	int nowCnt = 0, node;
	for (int i = 1; i <= N; i++)
	{
		q.push(i);
		m[i][0] = 1;
	}
	while (!q.empty()) {
		if (nowCnt >= 7)
		{
			break;
		}
		while (!q.empty())
		{
			node = q.front();
			q.pop();
				
			for (int j = 0; j < v[node].size(); j++)
			{
				int nxtN = v[node][j];
				m[nxtN][nowCnt + 1] += m[node][nowCnt];
				m[nxtN][nowCnt + 1] %= mod;
			}
		}
		nowCnt++;
		for (int j=1; j<=N; j++)
		{
			if (m[j][nowCnt])
			{
				q.push(j);
			}
		}
	}

	for (int j=1; j<=N; j++)
	{
		ans += m[j][7];
		ans %= mod;
	}
	cout << ans;
	return 0;
}

---

 

새해 기념으로 문제의 내용에 새해가 들어간 문제를 풀었다.

 

이 문제는 처음에 DP라고 생각하지 않고 풀어서 코드가 많이 더러워 졌다;;

queue를 이용한 이유가 방문하는 그래프로 풀었기 때문에...

 

새해 첫 날 부터 문제도 풀었으니 새해 복 많이 받아야겠다~

 

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