본문 바로가기
자료구조 l 알고리즘/Theory

DFS (깊이우선탐색)

DevJK 2018. 11. 29. 21:45

DFS(깊이 우선 탐색)

알고리즘 문제에서 BFS(너비 우선 탐색)과 더불어 굉장히 많이쓰이는 기법.

그래프에서 더 이상 나아갈 길이 보이지 않을 때까지 한 루트를 깊숙히 탐색하는 방법으로

더 이상 나아갈 길이 없을 때 이전 노드로 돌아가 끝까지 탐색.



1번 정점에서 출발했을 때 방문 순서는 1-2-4-8-5-6-3-7 이 된다.

5번 정점에서 는 더이상 방문할 곳이 없으므로 이전 노드인 8번으로 되돌아가서 다음 후보지인 6번으로 이동한다.

이처럼 현재 노드에서 갈 수 있는 지점까지 방문하고 갈 수 없으면 되돌아가는 방식. Memoization을 이용한 Backtracking에

응용될 수 있다.


크게 DFS를 구현할 때

1. 재귀호출

2. 스택

두 가지를 이용하여 구현할 수 있다.

다음은 위의 그림 예제를 c++로 구현해본 것.



  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <set>
#include <algorithm>
#include <stack>
using namespace std;

/*

    DFS 구현 복습.

*/

class DFS{
private:
    int size;
    set<int> *matrix;
    bool *visited;
public:
    DFS(int size){
        this->size = size;
        matrix = new set<int>[size+1];
        visited = new bool[size+1];
        fill(visited, visited+size, false);
    }
    //func
    void setPoint(int src, int dest){
        matrix[src].insert(dest);
        matrix[dest].insert(src);
    }
    void startDfs(int init, int w){
        string str = (w == 0) ? "recursive":"stack";
        cout << "==== DFS searching(" << str << ")... ====" << endl;
        if(w == 0){
            dfsRecursive(init);
        }else{
            dfsStack(init);
        }
        cout << '\n';
        cout << "==== DFS complete... ====" << endl;
    }
    void dfsRecursive(int init){
        //재귀 호출을 통한 DFS
        //for() 문 안에 재귀를 호출하는 방식이다.
        //이럴 경우 for문을 먼저 도는 것이 아니라 재귀함수 호출이 항상 우선시 되어
        //최대한 깊은 재귀함수까지 들어간다.(for문을 먼저 도는 것이 아님.)
        //만약 가장 깊은 재귀함수까지 호출되었다면 이전 함수에서 호출한 for문의 it가 증가되어
        //다음 정점을 찾으므로 자연스럽게 깊이우선탐색이 구현이 된다.
        //다만 보통 재귀함수로 DFS를 짰을때 탐색 효율면으로 비효율적인 경우가 많다.
        //특히 최단거리 계산 등의 문제에서는 DFS보다 BFS를 이용하는 것이 효율적임.
        cout << init << " ";
        visited[init] = true;
        for(auto it = matrix[init].begin(); it != matrix[init].end(); it++){
            if(!visited[*it]){
                dfsRecursive(*it);
            }
        }
    }
    void dfsStack(int init){
        //방문한 노드를 스택에 순차적으로 저장하고 해당 스택의 최상단 노드가
        //더이상 방문할 다음 노드가 없을때 해당 스택에서 노드를 pop 하고
        //다음 스택의 차상위 노드를 target으로 삼아 검색한다.
        //queue를 이용한 BFS와 코드가 비슷하다.
        //while 안에서 스택이 다 비워질때까지 지속.
        stack<int> st;
        int count = 0;
        bool flag = true;
        int target = 0;
        st.push(init);
        while(!st.empty()){
            if(flag){
                target = st.top();
                cout << target << " ";
                visited[target] = true;
                count++;
            }else{
                st.pop();
                if(st.empty()){
                    return;
                }
                target = st.top();
            }
            flag = false;
            for(auto it = matrix[target].begin(); it != matrix[target].end(); it++){
                if(!visited[*it]){
                    st.push(*it);
                    flag = true;
                    break;
                }
            }
        }
    }
    void memset(){
        fill(visited, visited+(size+1), false);
    }
};

int main(){
    DFS dfs(8);
    dfs.setPoint(1, 2);
    dfs.setPoint(1, 3);
    dfs.setPoint(2, 4);
    dfs.setPoint(2, 5);
    dfs.setPoint(3, 6);
    dfs.setPoint(3, 7);
    dfs.setPoint(4, 8);
    dfs.setPoint(5, 8);
    dfs.setPoint(6, 8);
    dfs.setPoint(7, 8);

    dfs.startDfs(1, 1);     //stack
    dfs.memset();
    dfs.startDfs(1, 0);     //recursive

    return 0;
}




 

티스토리툴바