[C++] BFS와 DFS

친구가 기초 알고리즘 과외를 한다고 하는게 갑자기 생각남.

1, 2 강의에 BFS, DFS 기초 탐색 및 응용

3 강의에 DP

4 강의에 다익스트라

내 생각에는 날로 쳐먹으려는게 확실함

그냥 갑자기 생각나서 예전 기억 더듬으며 위 내용 복습 해보려고함.

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);
}