[백준/C++] 1260번 DFS와 BFS

문제: www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

문제풀이

 

DFS와 BFS의 구현문제이다.

 

DFS는 재귀함수의 형식으로 구현했고

BFS는 queue를 이용하여 구현했다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int N,M,V;
int visited[1001] = {0,}; //방문여부
int link[1001][1001] = {0,}; //간선

void init(){ //dfs후 방문여부를 0으로 초기화하여 bfs를 진행
    for(int i=0; i<1001; i++)
        visited[i] = 0;
}

void dfs(int n){
    cout<<n<<" ";

    visited[n] = 1;

    for(int i=1; i<=N; i++){
        if(link[n][i]&&!visited[i])
            dfs(i);
    }
}

void bfs(int n){
    queue<int> q;
    q.push(n);

    while(!q.empty()){
        int newn = q.front();
        visited[newn] = 1;
        cout<<newn<<" ";
        q.pop();

        for(int i=1; i<=N; i++){
            if(link[newn][i]&&!visited[i]){
                visited[i] = 1;
                q.push(i);
            }
        }
    }

    

}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin>>N>>M>>V;

    for(int i=0; i<M; i++){
        int a, b;
        cin>>a>>b;
        link[a][b] = 1; //양방향 간선이므로 a->b
        link[b][a] = 1; //b->a 모두 1로 초기화
    }

    dfs(V);
    init();
    cout<<"\n";
    bfs(V);


    return 0;
}

 

 

결과