[ 백준 1260 ] DFS와 BFS (C++, DFS-BFS)

[문제보기]

1260번: DFS와 BFS

 

[해결과정]

 DFS, BFS 사용

 

[소스코드]

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;

int n, m, s;
int check[10005];
vector<int> v[10005];
queue<int> q;

void dfs(int node){
    cout << node << " ";
    for(int i=0; i<v[node].size(); i++){
        if(check[v[node][i]]==0){
            check[v[node][i]]=1;
            dfs(v[node][i]);
        }
    }
}

void bfs(){
    while(!q.empty()){
        int node = q.front();
        q.pop();
        
        cout << node << " ";
        
        for(int i=0; i<v[node].size(); i++){
            if(check[v[node][i]]==0){
                q.push(v[node][i]);
                check[v[node][i]]=1;
            }
        }
    }
}

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

 

[해결 과정 중 실수한 부분 / 잡담]

 연결 점들을 오름차순으로 정렬해야했음...

 

[관련 문제 혹은 비슷한 문제]

 없음