[DFS & BFS] 1260번 DFS와 BFS

1260번 DFS와 BFS

 

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

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다.

 

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

예제 입력

4 5 1
1 2
1 3
1 4
2 4
3 4

 

예제 출력

1 2 4 3
1 2 3 4

 

해결방법

그래프 탐색을 DFS 와 BFS 로 해보는 간단한 문제이다

 

만약 동시에 탐색가능하다면 인덱스 순으로 하라는 조건만 신경쓰면 어렵지 않은 문제이다

for(int i=1; i<=n; i++){
    sort(adj[i].begin(), adj[i].end());
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1001
#define INF 987654321
using namespace std;

int n,m,s;
int u,v;

bool chk[MAX];

vector<vector<int>> adj;

void dfs(int ind){
    chk[ind] = true;
    cout << ind << " ";
    
    // DFS
    for(int i=0; i<adj[ind].size(); i++){
        if(!chk[adj[ind][i]]){
            dfs(adj[ind][i]);
        }
    }
}

void bfs(){
    queue<int> q;
    q.push(s);
    chk[s] = true;
    cout << s << " ";
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        for(int i=0; i<adj[now].size(); i++){
            int nxt = adj[now][i];
            if(!chk[nxt]){
                q.push(nxt);
                chk[nxt] = true;
                cout << nxt << " ";
            }
        }
    }
    cout << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m >> s;
    
    adj.resize(n+1);
    
    for(int i=0; i<m; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for(int i=1; i<=n; i++){
        sort(adj[i].begin(), adj[i].end());
    }
    
    memset(chk, false, sizeof(chk));
    dfs(s);
    cout << "\n";
    
    memset(chk, false, sizeof(chk));
    bfs();
}