💡 그래프 이론/그래프 탐색/너비 우선 탐색/깊이 우선 탐색
Memory 1268KB Time 0ms Code Length 998B
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
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int comp_num;
int input_num;
int visited[101]= {0};
int map[101][101] = {0};
int bfs(int node, int cnt) {
visited[node] = 1;
queue<int> q;
q.push(node);
while (!q.empty()) {
int new_node = q.front(); q.pop();
cnt++;
for (int i = 1; i <= comp_num; i++) {
if (visited[i] == 1)continue;
if (map[new_node][i] == 0)continue;
visited[i] = 1;
q.push(i);
}
}
cnt--; // 처음꺼 하나 뺌
return cnt;
}
int dfs(int node, int cnt) {
visited[node] = 1;
for (int i = 1; i <= comp_num; i++) {
if (visited[i] == 1) continue;
if (map[node][i] == 0)continue;
cnt = dfs(i, cnt+1);
}
return cnt;
}
void input() {
scanf("%d", &comp_num);
getchar();
scanf("%d", &input_num);
getchar();
for (int i = 0; i < input_num; i++) {
int s, e;
scanf("%d %d", &s, &e);
getchar();
map[s][e] = map[e][s] = 1;
}
}
int main()
{
input();
printf("%d\n", dfs(1,0));
//printf("%d\n", bfs(1,0));
}
이 코드는 컴퓨터 네트워크에서의 그래프 연결 상태를 확인하는 프로그램이다.
input() 함수는 컴퓨터의 수와 연결된 컴퓨터 쌍의 수를 입력받고, 해당 컴퓨터들 간의 연결 상태를 map 배열에 저장한다.
dfs() 함수는 깊이 우선 탐색을 이용하여 특정 노드로부터 연결된 모든 노드를 방문하며 카운트한다. 재귀적으로 호출하여 연결된 모든 노드를 탐색한다.
bfs() 함수는 너비 우선 탐색을 이용하여 특정 노드로부터 연결된 모든 노드를 방문하며 카운트한다. 큐를 이용하여 연결된 노드를 순차적으로 탐색한다.
main() 함수에서는 입력을 받은 후 dfs() 함수를 호출하여 1번 컴퓨터와 연결된 모든 컴퓨터의 수를 출력한다.
따라서, 이 코드는 깊이 우선 탐색을 사용하여 1번 컴퓨터와 연결된 모든 컴퓨터의 수를 출력하는 프로그램이다.
