💡 너비 우선 탐색/그래프 이론/그래프 탐색/정렬
Memory 8304KB Time 120ms Code Length 911B
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
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int N, M, R;
vector<int> nodes[100001];
int visited[100001];
int order[100001];
void bfs(queue<int> &IQ) {
int cnt = 1;
order[R] = 1;
while (!IQ.empty()) {
int now_node = IQ.front(); IQ.pop();
visited[now_node] = 1;
for (int i = 0; i < nodes[now_node].size(); i++) {
int next_node = nodes[now_node][i];
if (visited[next_node] == 1) continue;
visited[next_node] = 1;
cnt++;
order[next_node] = cnt;
IQ.push(next_node);
}
}
}
int main() {
scanf("%d %d %d", &N, &M, &R);
for (int i = 0; i < M; i++) {
int u, v;
scanf(" %d %d", &u, &v);
nodes[u].push_back(v);
nodes[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
sort(nodes[i].begin(), nodes[i].end(), greater<int>());
}
queue<int> q;
q.push(R);
bfs(q);
for (int i = 1; i <= N; i++) {
printf("%d\n", order[i]);
}
}
이 코드는 입력으로 받은 노드와 간선 정보를 바탕으로 BFS(너비 우선 탐색) 알고리즘을 사용하여 시작 노드부터 연결된 노드들을 순서대로 방문하고, 방문한 순서를 order 배열에 저장하는 프로그램이다. 먼저 입력으로 받은 노드와 간선 정보를 바탕으로 인접 리스트를 생성하고, 각 노드의 연결된 노드들을 내림차순으로 정렬한다. 그 후, 시작 노드를 큐에 넣고 BFS 알고리즘을 통해 연결된 노드들을 방문하며 순서를 저장한다. 마지막으로 저장된 순서를 출력한다.
