[BOJ1260]BFS와 DFS

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

BFS와 DFS 기본 알고리즘 스크랩!

https://kmkidea.tistory.com/50

 

[C++] BFS와 DFS

BFS ? 

너비 우선 탐색

 

1) 시작 노드에서 자신의 자식 노드들을 모두 방문

 

2) 방문한 자식 노드 순서대로 1) 과정을 반복

 

 

DFS ? 

깊이 우선 탐색

 

1) 시작 노드에서 자식 노드 중 1개를 방문

 

2) 방문한 자식 노드에서 1)을 반복 (만약 방문했었던 노드일 경우 재방문 안함)

 

3) 현재 노드에서 더 이상 방문할 노드가 없을 경우 부모 노드로 이동-> 1)반복

 

 

예제를 들어 보면..

 

 

C++ 구현해보자

#include<bits/stdc++.h>

using namespace std;

int n,m,v;

bool visit[1005];

vector<int> path[1005];

queue<int> q;

 

void dfs(int v){

    for(int i=0;i<path[v].size();++i){

        if(!visit[path[v][i]]){

            visit[path[v][i]]=1;

            printf("%d ",path[v][i]);

            dfs(path[v][i]);

        }

    }

}

void bfs(int v){

    for(int i=0;i<path[v].size();++i){

        if(!visit[path[v][i]]){

            q.push(path[v][i]);

            visit[path[v][i]]=1;

        }

    }

    while(!q.empty()){

        int t = q.front();

        q.pop();

        printf("%d ",t);

        bfs(t);

    }

}

int main(){

    int x,y;

    scanf("%d%d%d",&n,&m,&v);

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

        scanf("%d%d",&x,&y);

        path[x].push_back(y);

        path[y].push_back(x);

    }

    for(int i=0;i<n;++i)

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

    visit[v]=1;

    printf("%d ",v);

    dfs(v);

    puts("");

    memset(visit,0,sizeof(visit));

    visit[v]=1;

    printf("%d ",v);

    bfs(v);