DFS & BFS

그래프 탐색 기법인 DFS와 BFS에 대해 알아보았다.

DFS

• 깊이 우선 탐색
• 그래프의 깊이 방향으로 먼저 탐색
• 쉽게 말하면 하나의 branch를 모두 탐색한 뒤에 다음 branch 탐색
• 그래프를 완전히 탐색할 때 주로 사용

방법

• 스택이나 재귀함수를 사용
• 노드 방문 여부를 체크하지 않으면 무한루프에 빠질 수도 있음
• 탐색 과정이 한없이 수행될 수도 있기 때문에 깊이제한을 둬야 함
• 깊이 제한에 도달할 때까지 목표노드를 발견하지 못하면 최근에 첨가된 노드의 부모노드로 돌아와 (백트레킹: backtracking) 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드 생성

장점

• 현 경로 상의 노드만 기억하므로 저장공간의 수요가 적음
• 목표노드의 깊이가 깊은 경우 다른 알고리즘보다 빠르게 목표노드를 찾을 수 있음

단점

• 해가 없는 경로에 빠질 가능성이 있음
• 얻어진 해가 최단경로가 된다는 보장이 없음

Code

• 재귀함수 사용

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 10
using namespace std;

int n,m,start;
bool visited[MAX]={0};
vector<int> graph[MAX];

void Input(){
    cin>>n>>m>>start;
    fill(visited, visited+n+1, false);
    for(int i=0; i<m; i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1; i<=n; i++){
        sort(graph[i].begin(), graph[i].end());
    }
}

void DFS(int cur){
    visited[cur]=true;
    cout<<cur<<" ";
    for(int i=0; i<graph[cur].size(); i++){
        int next=graph[cur][i];
        if(!visited[next])
            DFS(next);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    DFS(start);
    return 0;
}

• stack 사용

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#define MAX 10
using namespace std;

int n,m,start;
bool visited[MAX]={0};
vector<int> graph[MAX];

void Input(){
    cin>>n>>m>>start;
    fill(visited, visited+n+1, false);
    for(int i=0; i<m; i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1; i<=n; i++){
        sort(graph[i].begin(), graph[i].end());
    }
}

void DFS(int cur){
    stack<int> s;
    s.push(cur);
    visited[cur]=true;
    cout<<cur<<" ";
    while(!s.empty()){
        int current=s.top();
        s.pop();
        for(int i=0; i<graph[current].size(); i++){
            int next=graph[current][i];
            if(!visited[next]){
                cout<<next<<" ";
                visited[next]=true;
                s.push(current);
                s.push(next);
                break;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    DFS(start);
    return 0;
}

BFS

• 너비 우선 탐색
• 그래프의 너비 방향으로 먼저 탐색
• 쉽게 말하면 현재 노드에서 가까운 노드들을 우선적으로 탐색
• 최단 경로 탐색 or 임의의 경로 탐색에 주로 사용

방법

• 큐를 사용
• 탐색을 시작한 노드를 큐에 넣고 방문 처리
• 큐에서 노드를 꺼내고 해당 노드와 인접한 노드 중 방문 처리되지 않은 노드들을 모두 큐에 넣고 방문 처리

장점

• 출발 노드에서 목표 노드까지 최단 길이 경로 보장

단점

• 경로가 길다면 탐색 가지가 급격히 증가하여 많은 기억 공강 필요
• 해가 존재하지 않을 때, 그래프 전체를 탐색한 후 실패로 종료
• 무한 그래프의 경우 해를 찾지도, 끝내지도 못함

Code

• queue 사용

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 10
using namespace std;

int n,m,start;
bool visited[MAX]={0};
vector<int> graph[MAX];

void Input(){
    cin>>n>>m>>start;
    fill(visited, visited+n+1, false);
    for(int i=0; i<m; i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1; i<=n; i++){
        sort(graph[i].begin(), graph[i].end());
    }
}

void BFS(int cur){
    queue<int> q;
    q.push(cur);
    visited[cur]=true;
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        for(int i=0; graph[tmp].size(); i++){
            if(!visited[tmp]){
                q.push(graph[tmp][i]);
                visited[tmp]=true;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    BFS(start);
    return 0;
}