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

문제

---

그래프가 주어질 때, 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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#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;
}