DFS(깊이 우선 탐색)

DFS 에 대해 알아보자.

똑같은 그래프를 DFS로 탐색한다면 어떨까?
깊이 우선 탐색을 통해 탐색 순서를 알아보자.

DFS 란?

DFS (Depth-First-Search) 는 깊이 우선 탐색 이라고 하며, 재귀적으로 동작한다.
재귀적 이란 우리가 흔히 사용하는 Stack 처럼 함수를 차곡차곡 쌓아두는 것을 의미하며
더이상 사용되지 않을 때는 가장 최근에 올려진 함수부터 차근차근 빠지게 된다.

깊이 우선 이라는 말은 a와 b가 인접하고 있다고 가정해보자.
a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문한다.
쉽게 말해, b의 노드를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
참고로 이웃이 다수라면 값이 작은 노드부터 방문한다.
순서는 다음과 같다.

너비 우선 탐색

• Node 0

  • Node 1

    • Node 3

      • Node 2
      • Node 4

• Node 5

코드로 구현해보면 어떨까?

#include <iostream>
#include <vector>
using namespace std;
int number = 6;
int C[6]; 
vector<int> V[6]; 

void dfs(int x)
{
    if(C[x]) return;
    C[x] = true;
    cout << x << ' ';
    for(int i = 0; i < V[x].size(); i++)
    {
        int y = V[x][i];
        dfs(y);
    }
}

int main()
{
    V[0].push_back(1);
    V[0].push_back(4);
    V[0].push_back(5);
    
    V[1].push_back(3);
    V[1].push_back(4);

    V[2].push_back(1);

    V[3].push_back(2);
    V[3].push_back(4);

    dfs(0);

    return 0;
}

실행시키면 0 1 3 2 4 5 가 출력되는 것을 볼 수 있다.
그래프를 벡터의 로 표현하는 이유는 다음과 같다.

시작	도착	도착	도착
0	1	4	5
1	3	4	X

이렇게 벡터로 표현한 그래프를 시작 노드부터 반복을 통해 탐색하게 된다.
탐색을 한 노드는 방문처리 C[x] = true 를 해주고 방문처리가 된 노드는 다시는 방문하지 않는다.
이 떄 Stack(재귀)를 이용한다는 것을 잊지말자!!

관련문제 BFS 관련문제