문제
유아는 새해를 맞이하여 V.Nets의 자율 주행 자동차를 구매하였다. 유아는 새 차를 타고 바다로 가서 회를 잔뜩 먹고 올 것이다(유아는 감염병 예방을 위한 정부의 방역지침을 준수한다). 고속도로를 달리던 유아는 놀라 자빠질 수밖에 없었다. V.Nets의 자율 주행 시스템이 형편없었기 때문이다. V.Nets에 큰 배신감을 느낀 유아는 직접 자율 주행 자동차를 설계하기로 결심하였다.
곰두리차는 유아가 설계한 자율 주행 자동차이다. 곰두리차는 항상 인접한 정점 중 임의의 정점으로 이동한다. 유아는 출발점에서 도착점까지의 경로가 존재하고 시간이 무한하다면 곰두리차가 언제나 목적지에 도달할 수 있다고 믿고 있다. 유아는 문득 그래프가 주어졌을 때, 곰두리차가 지날 수 있는 경로가 몇 개인지 궁금해졌다.
하지만 유아는 이 문제를 풀지 못하였다. 문제의 난이도를 낮추기 위하여 유아는 경로상에서 동일한 정점 또는 간선을 재방문하는 것을 허용하였다.
그래프가 주어졌을 때, 곰두리차가 지날 수 있는 경로 중 길이가 7인 경로의 개수를 구하는 프로그램을 작성하시오. 곰두리차는 동일한 정점 또는 간선을 여러 번 지날 수 있다.
입력
첫 번째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.
이후 M개의 줄에 걸쳐 간선이 연결하는 두 정점 번호 u, v가 주어진다.
주어지는 간선은 양방향 간선이며, 모든 입력은 공백으로 구분되어 주어진다.
출력
첫 번째 줄에 곰두리차가 지날 수 있는 경로 중 길이가 7인 경로의 개수를 출력한다. 답이 매우 커질 수 있으므로 109 + 7로 나눈 나머지를 출력한다.
제한
- 2 ≤ N ≤ 100,000
- 1 ≤ M ≤ min(N × (N - 1) / 2, 100,000)
- 1 ≤ u, v ≤ N
- u ≠ v
- 입력으로 주어진 그래프에는 중복 간선이 존재하지 않는다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<cstdio>
#include <vector>
#define mod 1000000007
using namespace std;
vector<int> node[100001];
int dp[8][100001];
int cnt;
int main() {
int n, m, u, v;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
node[u].push_back(v);
node[v].push_back(u);
dp[0][u] = dp[0][v] = 1;
}
for (int i = 1; i <= 7; i++) {
for (int j = 1; j <= n; j++) {
for (int x:node[j]) {
dp[i][x] = (dp[i][x] % mod + dp[i - 1][j] % mod) % mod;
}
}
}
for (int i = 1; i <= n; i++)
cnt = (cnt % mod + dp[7][i] % mod) % mod;
printf("%d\n", cnt);
return 0;
}
|
cs |
dfs + dp로 풀어보려고 했는데 간단하게 dp로 풀리는 문제였다.
dp[i][j]는 길이가 i이고 마지막 정점이 j인 경로의 수라고 생각하면 된다.
21번째 줄의 반복문을 보면 길이가 i이고 마지막 정점이 x인 경로의 수는 길이가 i-1이고 마지막 정점이 x와 연결된
경로의 수라는 것을 알 수 있다.
계산하면서 모듈러 연산만 빠뜨리지 않는다면 생각보다 쉬운 문제였다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 2143 두 배열의 합 (0) | 2021.02.26 |
|---|---|
| 백준 온라인 저지 16397 탈출 (0) | 2021.02.25 |
| 백준 온라인 저지 1025 제곱수 찾기 (0) | 2021.02.20 |
| 백준 온라인 저지 17836 공주님을 구해라! (0) | 2021.02.15 |
| 백준 온라인 저지 12789 도키도키 간식드리미 (0) | 2021.02.10 |
