💡 깊이 우선 탐색/그래프 이론/그래프 탐색/정렬
Memory 14300KB Time 128ms Code Length 628B
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
#include <stdio.h>
#include <queue>
using namespace std;
int N, M, R;
priority_queue<int, vector<int>,greater<int>> map[100001];
int visited[100001];
int order[100001];
int cnt = 1;
void dfs(int node) {
visited[node] = 1;
order[node] = cnt;
while (!map[node].empty()) {
int next_node = map[node].top(); map[node].pop();
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, v;
scanf(" %d %d", &u, &v);
map[u].push(v);
map[v].push(u);
}
dfs(R);
for (int i = 1; i <= N; i++) {
printf("%d\n", order[i]);
}
}
이 코드는 주어진 그래프에서 깊이 우선 탐색(DFS)을 수행하여 각 노드를 방문하는 순서를 구하는 프로그램이다.
입력으로는 노드의 개수 N, 간선의 개수 M, 시작 노드 R이 주어진다.
각 노드에 연결된 다른 노드들을 우선순위 큐에 저장한다. 우선순위 큐는 작은 값부터 꺼내올 수 있는 구조이다.
방문한 노드를 표시하기 위한 visited 배열과 각 노드의 방문 순서를 저장하기 위한 order 배열을 초기화한다.
dfs 함수를 호출하여 시작 노드부터 깊이 우선 탐색을 수행한다. 방문한 노드는 visited를 1로 표시하고, 방문 순서를 cnt에 저장한다.
현재 노드와 연결된 다음 노드를 우선순위 큐에서 꺼내어 방문하지 않은 경우에만 다음 노드로 이동하며, cnt를 증가시키고 재귀적으로 dfs 함수를 호출한다.
모든 노드를 방문한 후, 각 노드의 방문 순서를 출력한다.
즉, 이 코드는 주어진 그래프에서 시작 노드부터 깊이 우선 탐색을 수행하여 각 노드의 방문 순서를 출력하는 것이다.
