[Algorithm] DFS(깊이 우선 탐색)

DFS란?

깊이 우선 탐색(Depth First Search)는 깊은 것을 우선적으로 탐색하는 방법이다.

스택을 사용한다.

DFS원리

먼저 시작 node를 스택에 넣어주고, 방문처리를 해준다.

그 후, 아래의 과정을 반복한다.
1. 스택의 가장 위에 있는 node(가장 최근에 들어온 node)를 확인한다.
2. 그 node의 인접 node 중 방문하지 않은 node가 있다면 그 node를 스택에 넣고 방문처리한다. 만약, 방문하지 않은 node가 없다면 스택에서 최상단 node를 뺀다.

구현해보기

스택을 구현해서 하는 것이 정석이지만, 컴퓨터는 구조적으로 스택의 원리를 사용하기 때문에 재귀함수만으로 구현할 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int number = 7; // node의 개수
int checked[7]; // 각 node의 방문처리를 위한 배열 
vector<int> a[8]; // node의 인접관계를 나타내기 위한 벡터

void dfs(int x) {
    if(checked[x]) return; // 해당 node를 이미 방문했다면 return
    checked[x] = true; // 처음 방문하는 것이면 방문처리

    cout << x << ' '; // 해당 node 출력

    for(int i=0;i<a[x].size();i++){ // 해당 node와 인접한 node를 하나씩 방문하면서 dfs 실행
        int y = a[x][i];
        dfs(y);
    }
}

int main(void) {

    a[1].push_back(2);
    a[2].push_back(1);

    a[1].push_back(3);
    a[3].push_back(1);

    a[2].push_back(3);
    a[3].push_back(2);

    a[2].push_back(4);
    a[4].push_back(2);

    a[2].push_back(5);
    a[5].push_back(2);

    a[3].push_back(6);
    a[6].push_back(3);

    a[3].push_back(7);
    a[7].push_back(3);

    a[4].push_back(5);
    a[5].push_back(4);

    a[6].push_back(7);
    a[7].push_back(6);

    dfs(1);

    return 0;
}

DFS 그 자체보다, 다른 알고리즘에 많이 쓰인다.

reference: https://www.youtube.com/watch?v=l0Rsu7dziws&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=17