문제 링크 : https://www.acmicpc.net/problem/30206
30206번: 차량 배치
첫 번째 줄에 지점의 개수 $N$과 도로의 개수 $M$이 공백으로 구분되어 정수로 주어진다. $(1 \le N \le 200\,000;$ $N-1 \le M \le \min(\frac{N(N-1)}{2}, 200\,000))$ 이후 $M$개의 줄에 걸쳐 각 도로가 잇는 서로 다른
www.acmicpc.net
작성 코드
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[200001];
bool visited[200001];
long long levelCount[200001];
int maxLevel = 0;
long long result = 0;
queue<pair<int, int>> q;
void BFS(int t)
{
q.emplace(t, 0);
visited[t] = true;
result = 2; // 1번 노드에서 가능한 배치
while (!q.empty())
{
int now = q.front().first;
int level = q.front().second;
q.pop();
// 한 레벨에 하나만 배치해야 하므로 노드 갯수를 센다.
// 다음 줄의 가능한 배치 수 곱하기 (+1은 배차가 없는 경우를 셈)
for (int i = 0; i < v[now].size(); ++i)
{
int next = v[now][i];
if (!visited[next])
{
q.emplace(next, level+1);
levelCount[level+1]++;
visited[next] = true;
maxLevel = max(maxLevel, level+1);
}
}
}
}
int main()
{
/*ios::sync_with_stdio(false);
cin.tie(NULL);*/
int N, M; // 지점의 개수, 도로의 개수
int a, b;
cin >> N >> M;
for (int i = 0; i < M; ++i)
{
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
BFS(1);
for (int j = 1; j <= maxLevel; ++j)
{
result = result * (levelCount[j] + 1) % 1000000007;
}
if (result >= 1)
{
result--;
}
cout << result;
}
|
cs |
풀이
문제에 있는 조건을 해석해보자
모든 차량은 최단 경로를 통해 동일한 속도로 이동한다 == 거리는 도달 시간과 비례한다.
같은 시간에 도달하면 충돌 사고가 발생한다 == 같은 시간에는 하나의 차량만 존재해야한다.
이를 통해 한 레벨당 하나씩만 선택이 가능한 노드를 작성할 수 있다.
예시 그림으로 풀어보자면 이와 같다.
- 도착 시간 == 노드 레벨 이므로
ㄴ1레벨에서 가능한 경우의 수는 1번 지점 선택 혹은 차량 없음
ㄴ2레벨에서 가능한 경우의 수는 두 지점 (2,3번) 중 하나를 선택 혹은 차량 없음
ㄴ3레벨에서 가능한 경우의 수는 네 지점 (4,5,6,7번) 중 하나를 선택 혹은 차량 없음
매 레벨당 경우의 수는 노드 레벨의 노드 갯수 + 1와 같다.
총 차량의 경우의 수는 이를 곱해주면 된다.
단, 문제에서 최소 하나의 차량이 배치되어야한다고 했으므로 모든 노드가 비어있는 경우를 제외한다 (결과 -1)
각 층의 노드 갯수는 BFS 탐색을 통하여 최단 거리를 탐색할 수 있다.
'백준 > C++' 카테고리의 다른 글
| [백준] 29155 개발자 지망생 구름이의 취업 뽀개기 (C++) (0) | 2023.09.08 |
|---|