본문 바로가기
[C++] 알고리즘 교육/19. BFS(기본)

[알고리즘 19.1.1] BFS - 깊이우선탐색과 너비우선탐색

by 안산학생 2019. 8. 12.

문제


그래프가 주어질 때, 0번 정점을 시작으로 하여 깊이우선탐색과 너비우선탐색의 결과를 출력하는 프로그램을 작성하시오. 단, 노드를 방문할 때는 노드 번호가 작은 순서대로 방문한다고 하자.

 

입력


첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다. 정점의 번호는 0번부터 N-1번까지이다.

 

출력


첫 번째 줄에 깊이우선탐색 결과, 두 번째 줄에 너비우선탐색 결과를 출력한다.

 

예제 입력

9 12

0 1

0 2

0 3

1 5

2 5

3 4

4 5

5 6

5 7

5 8

6 7

7 8

예제 출력

0 1 5 2 4 3 6 7 8

0 1 2 3 5 4 6 7 8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
const int MAX = 1005;
 
int n, m;
vector <int> arr[MAX];
bool check[MAX]={0,};
bool check2[MAX]={0,};
 
queue <int> q;
 
void BFS(){
  if(q.empty()){
    return;
  }
  
  int num = q.front();
  q.pop();
  check2[num] = true;
  cout<<num<<" ";
  
  for(int i=0; i<arr[num].size();i++){
    if(check2[arr[num][i]]==false){
      q.push(arr[num][i]);
      check2[arr[num][i]] = true;
    }
  }
  
  if(!q.empty()){
    BFS();
  }
}
 
void DFS(int num){
  check[num] = true;
  cout<<num<<" ";
  
  for(int i=0; i<arr[num].size();i++){
    if(check[arr[num][i]] == false){
      DFS(arr[num][i]);
    }
  }
}
 
int main(){
  
  cin>>n>>m;
  
  int a, b;
  for(int i=0; i<m; i++){
    cin>>a>>b;
    arr[a].push_back(b);
    arr[b].push_back(a);
  }
  
  for(int i=0;i<n;i++){
    sort(arr[i].begin(),arr[i].end());
  }
  
  DFS(0);
  printf("\n");
  
  q.push(0);
  BFS();
  
  return 0;
}
 

댓글