[알고리즘] DFS(Depth First Search) 알고리즘

안녕하세요  감자코딩에 감자개발자입니다.

이번에는 살펴볼 알고리즘 개념은 바로 "DFS(Depth First Search)" 입니다.

* DFS(Depth First Search) 알고리즘

1. 깊이우선탐색이란 트리 및 그래프 등을 탐색하는 알고리즘이다.
2. 특정 노드를 출발하여 깊게 들어 갈 수 있을때 까지 들어가고 들어 갈 곳이 없다면 다시 나오는 알고리즘이다.
3. 깊게 들어간다해서 깊이 우선 탐색, 스택을 이용하여 구현한다.(재귀를 많이 사용함)

* DFS탐색순서 

DFS의 탐색순서를 보면 깊이 순서에따라서 방문하는 것이 달라지는것을 볼 수 있습니다. 

그림에서 주어진 순서대로 탐색을 하게 되는것을 알고 계시면 될것같습니다.

* DFS 알고리즘 구현 로직

// dfs call

void dfs(int num)

{

    printf("%d ", num);     // 값 출력

    for (int i = 1; i <= n; i++)    {        // n 모든정점의 개수

        // graph 갈수있고, 방문하지 않은경우

        if (graph[num][i] && visit[i] == 0) {

            visit[i] = 1;

            dfs(i);            // recursive call

        }

    }

}

DFS 대표적인 구현은 = 재귀적 함수 호출(Recursive Call) 

계속해서 자기자신을 호출하면서, 재귀호출을 통한 Return값을 얻게되는 로직입니다.

모든 정점을 하나씩 탐색하여 연결된 간선이고, 아직 체크되어있지않은 정점일 경우에 체크 visit = 1 그리고, 다시 재귀호출을 통하여 값을 얻게됩니다.

이에따라, 기본적인 DFS 개념 및 로직을 살펴보았습니다.

감사합니다.