💡 너비 우선 탐색/깊이 우선 탐색/그래프 이론/그래프 탐색
Memory 3352KB Time 2228ms Code Length 999B
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
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
vector<int> graph[10001];
vector<int> vc;
void init() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
int end, start;
cin >> end >> start;
graph[start].push_back(end);
}
}
int bfs(int node) { // 한번에 들를수 있는 갯수찾기
int cnt = 0;
queue<int> q;
int visited[10001] = {0};
q.push(node);
visited[node] = 1;
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = 0; i < graph[now].size(); i++) {
if (visited[graph[now][i]])continue;
visited[graph[now][i]] = 1;
q.push(graph[now][i]);
cnt++;
}
}
return cnt;
}
int main() {
init();
int maxV = 0;
for (int i = 1; i <= N; i++) {
int result = bfs(i);
if (maxV < result) { // 초기화
maxV = result;
vc.clear();
vc.push_back(i);
}
else if (maxV == result) {
vc.push_back(i);
}
}
sort(vc.begin(), vc.end(), less<int>());
for (auto a : vc) {
cout << a << " ";
}
}
이 코드는 그래프를 이용하여 각 노드에서 출발하여 도달할 수 있는 노드의 수를 구하는 BFS 알고리즘을 구현한다.
init 함수는 입력으로 받은 노드의 수(N)와 간선의 수(M)를 받고, 그래프를 초기화한다.
bfs 함수는 주어진 노드에서 시작하여 도달할 수 있는 노드의 수를 계산하는 함수이다. 방문한 노드를 표시하고, 해당 노드와 연결된 노드를 큐에 넣어가며 탐색한다.
main 함수에서는 모든 노드를 순회하며 bfs 함수를 호출하여 각 노드에서 도달할 수 있는 노드의 수를 구하고, 이를 비교하여 최대값을 찾는다. 최대값을 가지는 노드들을 vc 벡터에 저장하고, 이를 정렬하여 출력한다.
