#1260번 DFS와 BFS (C++)

링크 : www.acmicpc.net/problem/1260

1260번: DFS와 BFS

DFS와 BFS의 기본 개념을 정리하기에 좋은 문제이다.

DFS는 재귀, BFS는 큐로 풀었으며, 기본 개념을 익히는 문제인 관계로 해설은 적지 않겠다. 

 

다만 한 가지 주의할 점은, 방문할 수 있는 노드가 여러개 연결 된 경우 번호가 작은 것을 먼저 방문해야한다는 조건이다.

이 때문에 sort 함수로 미리 배열을 정렬해두었다.

 

2차원 배열(벡터)을 초기화 한 것은 처음인데, 이번 문제를 통해 활용할 수 있게 되었다.

 

---

 

for(int i=1; i<=n; i++){

    sort(v[i].begin(), v[i].end());

}

 

---

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int n = 0, m = 0, s = 0, temp = 0;
vector <int> v[1001];
bool ch[1001] = {false,};

void bfs(int x){
    queue<int> q;
    q.push(x);
    ch[x] = true;
    while(!q.empty()){
        temp = q.front();
        cout << temp << " ";
        q.pop();
        for(int i=0; i<v[temp].size(); i++){
            if(!ch[v[temp][i]]){
                ch[v[temp][i]] = true;
                q.push(v[temp][i]);
            }
        }
    }
}

void dfs(int x){
    cout << x << " ";
    ch[x] = true;
    for(int i=0; i<v[x].size(); i++){
        if(!ch[v[x][i]]){
            dfs(v[x][i]);
        }
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a = 0, b = 0;
    cin >> n >> m >> s;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1; i<=n; i++){
        sort(v[i].begin(), v[i].end());
    }
    dfs(s);
    memset(ch,false,sizeof(ch));
    cout << "\n";
    bfs(s);
    cout << "\n";

    return 0;
}