dfs와 bfs의 기본적인 흐름[백준 1260번]

 

 

#include<iostream>

#include<queue>

using namespace std;

bool check[1001];

int a[1001][1001];

int n, m;

void dfs(int x){ //x를 방문한다.

    check[x] = true;  //x를 방문처리하고

    printf("%d ", x);   //x를 출력

    for(int i=1; i<=n; i++){    // i를 처음부터 끝까지 순회하는데

        if(a[x][i] == 1 && check[i] == false){  //x에서 i로 가는 간선이 있고, i를 방문하지 않았다면

            dfs(i); //i를 방문한다.

        }

    }

}

int main(){

    int v;

    cin>>n>>m>>v;

    while(m--){

        int p, q;

        cin>>p>>q;

        a[p][q]=1;

        a[q][p]=1;

    }

    dfs(v);

    cout<<'\n';

    for(int i=0; i<1001; i++){

        check[i] = false;

    }

    queue<int> q;   //큐를 생성하고

    check[v]=true;  //지금 있는 곳을 방문처리 하고

    q.push(v);  // 큐에 삽입한 후

    while(!q.empty()){  // 큐가 빌때까지

        int y = q.front();  // 지금 있는 곳을 적어놓은 다음

        q.pop();    //큐를 pop한 후

        printf("%d ",y);    // y를 출력하고

        for(int i=1; i<=n; i++){    //연결되어 있는 간선을 찾기위해

            if(a[y][i] == 1 && check[i] == false){  //y에서 i로 가는 간선이 있고 i를 방문하지 않았다면

                check[i]=true;  // 방문처리하고

                q.push(i);  //i를 큐에 삽입한다.

            }

        }

    }

    return 0;

}

문제 출처 : https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS