Algorithm/BOJ
DFS와 BFS
jhg0406
2020. 2. 18. 17:17
|
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
//1260 - DFS와 BFS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, S;
vector<vector<int>> adj;
vector<bool> visit;
void init()
{
cin >> N >> M >> S;
adj = vector<vector<int>>(N+1);
visit = vector<bool>(N+1, false);
int x, y;
for(int i = 0; i<M; ++i)
{
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for(int i = 1; i<=N; ++i)
sort(adj[i].begin(), adj[i].end());
}
void dfs(int here)
{
cout << here << " ";
visit[here] = true;
for(int i = 0; i<adj[here].size(); ++i)
{
int there = adj[here][i];
if(!visit[there])
dfs(there);
}
}
void bfs()
{
visit = vector<bool>(N+1, false);
queue<int> q;
q.push(S);
visit[S] = true;
while(!q.empty())
{
int here = q.front();
q.pop();
cout << here << " ";
for(int i = 0; i<adj[here].size(); ++i)
{
int there = adj[here][i];
if(!visit[there])
{
visit[there] = true;
q.push(there);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
dfs(S);
cout << "\n";
bfs();
}
|
cs |
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와 BFS
기본 DFS, BFS문제 입니다!
