💡 깊이 우선 탐색/그래프 이론/그래프 탐색/정렬
Memory 10388KB Time 132ms Code Length 727B
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
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, R;
vector<int> vc[100001];
int visited[100001];
int order[100001];
int cnt = 1;
void dfs(int node) {
visited[node] = 1;
order[node] = cnt;
for (int i = 0; i < vc[node].size(); i++) {
int next_node = vc[node][i];
if (visited[next_node] == 1) continue;
cnt++;
dfs(next_node);
}
}
int main() {
scanf("%d %d %d", &N, &M, &R);
for (int i = 0; i < M; i++) {
int u, c;
scanf(" %d %d", &u, &c);
vc[u].push_back(c);
vc[c].push_back(u);
}
// 정렬거치기
for (int i = 1; i <= N; i++) {
sort(vc[i].begin(), vc[i].end(), greater<int>());
}
dfs(R);
for (int i = 1; i <= N; i++) {
printf("%d\n", order[i]);
}
}
이 코드는 DFS(깊이 우선 탐색) 알고리즘을 사용하여 그래프의 노드를 방문하는 순서를 찾는다. 먼저 입력으로 받은 그래프 정보를 인접리스트에 저장하고, 각 노드를 깊이 우선 탐색하여 방문 순서를 order 배열에 저장한다. 이때, 이미 방문한 노드는 visited 배열을 통해 확인하고, 방문 순서는 cnt 변수를 통해 증가시킨다. 최종적으로 모든 노드의 방문 순서를 출력한다.
