728x90
너비 우선 탐색이란, 임의의 노드 또는 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다.
구현:
(1) 시작점을 큐에 삽입
(2) 시작점을 색칠, BFS 시작 (while 문)
(3) 큐에서 하나를 뺀다. pop 된 node가 현재 위치!
(4) 인접 노드에 방문 했는지 확인
- 방문 안했으면, 색칠하고 큐에 삽입
(5) 모두 완료 했으면 (3)으로 돌아간다.
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
75
76
77
78
79
80
81
82
83
84
85
86
87
|
/*
너비우선탐색 (BFS)
(1) -----(2) ------(6)
\ / \ /
\ / (4) ---(5)
\ / / \
(3)- (7)-(8)-(9)
----------------------------------
DFS : 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> 6 -> 8 -> 9
BFS : 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 5 -> 8 -> 9
9 12
1 2
1 3
2 4
2 6
3 7
4 5
4 7
4 8
5 6
7 8
8 9
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100005
vector<int> myGraph[MAX];
queue <int> Queue;
bool visited[MAX];
int n, m;
void BFS(){
// 1. 시작점을 큐에다가 삽입한다.
// 2. 시작점을 색칠한다.
//BFS 시작!
Queue.push(1);
visited[1]=true;
int current = Queue.front();
Queue.pop();
cout<<current<<" ";
for(int i = 0; i<myGraph[current].size(); i++){
int next = myGraph[current][i];
// current -- next
if(!visited[next]){
visited[next] = true;
}
}
}
}
int main(){
cin>>n>>m;
for(int i = 0; i<m; i++){
int a, b;
cin>>a>>b;
myGraph[a].push_back(b);
myGraph[b].push_back(a);
}
BFS();
return 0;
}
//결과: 0 1 2 3 5 4 6 7 8
|
728x90
'Algorithm Study > SW역량테스트' 카테고리의 다른 글
문자열 뒤집기(고급) (0) | 2020.06.22 |
---|---|
(동적계획법) 연속 부분 최대합L (0) | 2020.04.30 |
다익스트라 알고리즘(Dijkstra algorism) (0) | 2020.03.27 |
Card game (0) | 2020.03.03 |
최대공약수(GCD) 최소공배수(LCM) 출력하기 (0) | 2019.12.27 |
댓글