[백준 1260] DFS와 BFS

0. 제목

• 백준 1260 DFS와 BFS
• BOJ 1260 DFS와 BFS
• C++ 1260 DFS와 BFS

---

1. 문제

https://www.acmicpc.net/problem/1260

---

2. 풀이

• 먼저 탐색을 완료했는지 여부를 체크하는 checked 배열을 선언한다.
• 그래프를 생성해줄 때는 vector를 이용해서 선언해준다. 연결되어 있는 점들을 해당 vector에 push_back 해줌으로써 원소로 추가해준다.
• 그렇게 그래프를 생성한 후 오름차순으로 정렬해주어야 한다. 그 이유는 정점이 여러 개인 경우에 작은 번호부터 먼저 방문하기 때문이다.
• DFS의 경우에는 이미 탐색 완료를 하였으면 리턴하고 탐색하지 않았으면 탐색상태를 true로 바꿔준 후, 출력해준다. 그리고 그 점에 연결되어 있는 점들을 재귀적으로 다시 탐색한다.
• BFS의 경우에는 queue를 이용하는데 먼저 queue에 시작점을 넣고 checked 배열을 true로 바꿔준다. 그 후 queue가 빌때까지 다음을 반복한다. 
• 가장 처음 원소를 pop해준 후, 출력한다. 그 후, 해당 점에 연결되어 있는 점들을 순서대로 q에 넣어준다. 넣은 점들은 모두 탐색완료한 것이기때문에 checked[q에 들어간원소] = true 로 바꾸어준다.
• DFS 실시한 후 BFS를 하기 전에 반드시 checked 배열의 원소 값들은 모두 false 값으로 초기화 시켜야 한다.
• #include <queue>를 해주니 #include <vector> 를 하지 않아도 vector 사용이 가능하였다.
• memset은 <cstring> 라이브러리에 있다. 

---

3. 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int checked[1001];
vector<int> a[1001];
 
void dfs(int start);
void bfs(int start);
 
int main(int argc, const char * argv[]) {
    int N, M, V;
    int j, k;
    
    //그래프 생성
    cin >> N >> M >> V;
    for(int i = 0; i < M; i++){
        cin >> j >> k;
        a[j].push_back(k);
        a[k].push_back(j);
    }
    
    //정점이 여러 개인 경우에 작은 번호부터 먼저 방문하기 때문에 정렬해준다.
    for(int i = 1; i <= N; i++){
        sort(a[i].begin(), a[i].end());
    }
    
    dfs(V);
    cout << '\n';
    memset(checked, 0, sizeof(checked));    // #include <cstring>
    bfs(V);
    cout << '\n';
    
    return 0;
}
 
void dfs(int x){
    if(checked[x]) return;
    checked[x] = true;
    cout << x << ' ';
    unsigned long size = a[x].size();
    for(int i = 0; i < size; i++){
        int y = a[x][i];
        dfs(y);
    }
}
 
void bfs(int start){
    queue<int> q;
    q.push(start);
    checked[start] = true;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        cout << x << " ";
        unsigned long size = a[x].size();
        
        for(int i = 0; i < size; i++){
            int y = a[x][i];
            if(!checked[y]){
                q.push(y);
                checked[y] = true;
            }
        }
    }
}