그래프
DFS와 BFS, 촌수 계산
4gats
2023. 2. 18. 14:48
목적
임의의 정점에서 시작해 연결되어 있는 모든 정점을 1번씩 방문하는 것
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
DFS with Stack(재귀함수)
시간 복잡도 O(V+E) = O(E)
BFS with Queue
큐에 넣을 때 check 처리
시간 복잡도 O(E)
|
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
|
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
vector<int> a[1001];
bool check[1001];
void dfs(int node) {
check[node] = true;
printf("%d ", node);
for (int i = 0; i < a[node].size(); i++) {
int next = a[node][i];
if (check[next] == false) {
dfs(next);
}
}
}
void bfs(int start) {
queue<int> q;
memset(check, false, sizeof(check));
check[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
printf("%d ", node);
for (int i = 0; i < a[node].size(); i++) {
int next = a[node][i];
if (check[next] == false) {
check[next] = true;
q.push(next);
}
}
}
}
int main() {
int n, m, start;
scanf("%d %d %d", &n, &m, &start);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
a[u].push_back(v);
a[v].push_back(u);
}
//오름차순으로 나와야하기 때문에! for (int i = 1; i <= n; i++) {
sort(a[i].begin(), a[i].end());
}
dfs(start);
puts("");
bfs(start);
puts("");
return 0;
}
|
cs |
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
이 문제도 똑같다. vector를 이용해서 연결리스트를 만들어 bfs를 하자
|
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 <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> f[104];
int dist[104];
bool check[104];
int main()
{
int n;
cin >> n;
int start, end;
cin >> start >> end;
int input;
cin >> input;
for (int i = 0; i < input; i++)
{
int u, v;
cin >> u >> v;
f[u].push_back(v);
f[v].push_back(u);
}
queue<int> q;
check[start] = true;
q.push(start);
dist[start] = 0;
while (!q.empty())
{
int node = q.front();
q.pop();
for (int i = 0; i < f[node].size(); i++)
{
int next = f[node][i];
if (check[next] == false)
{
check[next] = true;
dist[next] = dist[node] + 1;
q.push(next);
}
}
}
if (dist[end] == 0)
{
cout << -1 << '\n';
}
else
{
cout << dist[end] << '\n';
}
}
|
cs |