깊이 우선 탐색(Depth First Search)을 알아보자 (feat.JS)

오늘은 바로 어제 알아봤던 너비 우선 탐색의 애인과 같은 길찾기 알고리즘인 깊이 우선 탐색(DFS)에 대해서 공부해보겠습니다. 먼저 너비 우선 탐색과 같이 깊이 우선 탐색(DFS: Depth First Search) 명칭의 의미를 확인해보겠습니다.

 

 

먼저 너비 우선 탐색을 보지 않으셨다면 먼저 보고 오시는걸 추천드립니다.

 

 

2022.07.31 - [컴공생의 Knowledge/Algoritm Notion] - 너비 우선 탐색(Breadth First Search)을 알아보자 (feat.JS)

너비 우선 탐색(Breadth First Search)을 알아보자 (feat.JS)

 

 

깊이 우선 탐색 (DFS: Depth First Search)

깊이 우선 탐색(DFS)는 Depth(깊이)을 우선적으로 탐색하여 길을 찾아가는 알고리즘입니다. 여기서 깊이의 의미는 말 그대로 점점 더 깊은 곳이라는 것을 뜻합니다. 그럼 더 자세한 정의에 대해서 확인해보겠습니다.

 

 

 

 

◎ 깊이 우선 탐색(DFS)의 정의

깊이 우선 탐색은 Depth First Search로 깊이를 우선으로 탐색을 진행하는 알고리즘입니다.

즉, 한번 선택한 길로 갈 수 있는한 깊게 탐색해보는 것을 우선으로 하는 탐색 방법으로 시작지점부터 멀리 갔다가 가까이 왔다가 반복하면서 복잡한 길을 찾고자 할 때 반복될 수 있다는 점이 특징입니다.

DFS 알고리즘은 모든 노드를 방문하고자 할 때 많이 활용되는 알고리즘입니다.

 

 

아래는 간단하게 연결되어있는 여러 지점들 사이에서 A 지점을 시작으로 모든 지점을 탐색하는 길을 깊이 우선 탐색(DFS)을 통해 찾아본 길을 나타낸 것입니다. 

 

 

 

 

 

 

◎ 깊이 우선 탐색(DFS)의 특징

• 재귀 함수를 활용하여 구현
  • 순환 알고리즘 형태를 띈다.
  • 알고리즘이 직접적이므로 구현이 쉽다.
• 모든 노드에 대한 방문 확인을 탐색하는데 최적 알고리즘
• 노드 방문 여부에 대해서 반드시 체크 필요
  • 체크하지 않을 경우, 무한 루프에 빠질 수 있다.

 

 

어제 공부했던 너비 우선 탐색(BFS)와 특징을 비교하였을 때, 길 찾기 알고리즘이라 그런지 노드 방문 여부에 대한 체크는 필수라는 부분이 공통점이 있었습니다.

 

 

 

 

◎ 깊이 우선 탐색(DFS)의 탐색 과정

① A에서 시작 → B로 이동	② B에서 시작 → C로 이동
③ C에서 시작 → D로 이동	④ D에서 시작 → C로 Backtracking
⑤ C에서 시작 → B로 Backtracking	⑥ B에서 시작 → A로 Backtracking
⑦ A에서 시작 → 모든 지점 방문으로 탐색 종료	⑧ 탐색 경로 (A-B-C-D)

 

 

위 동작은 각 위치별 갈 수 있는 경로를 확인 후 순서대로 방문했다가 돌아왔다가를 반복하면서 길을 탐색하는 과정이었습니다. 깊이 우선 탐색 알고리즘을 통해 얻은 탐색 경로가 어떻게 위와 같이 구해지는지, DFS 알고리즘에 대해 동작을 확인해보겠습니다.

 

 

 

 

◎ 깊이 우선 탐색(DFS)의 알고리즘

1. 시작 노드를 방문한다.
   • 시작 노드의 방문을 표시한다.
2. 시작 노드와 인접한 노드들을 차례로 순회한다.
   
   • 인접한 노드를 이전에 방문했다면 방문하지 않는다.
   • 이전에 방문하지 않은 노드라면 해당 노드를 시작 노드로 한다.
     (이 노드를 시작 노드로하여 DFS을 다시 시작한다.)
3. 시작 노드의 인접한 노드를 모두 탐색했다면 탐색을 종료한다.

 

 

그럼 위의 깊이 우선 탐색 알고리즘을 토대로 직접 JavaScript로 구현해보도록 하겠습니다.

 

 

 

 

◎ 깊이 우선 탐색(DFS)의 구현(JavaScript)

다음은 위에서 깊이 우선 탐색으로 탐색 과정으로 보여준 예시의 그래프 형태를 코드로 구현하여 깊이 우선 탐색 알고리즘 코드를 작성해보았습니다.

 

const GRAPH = {
    A: ["B", "C"],
    B: ["A", "C", "D"],
    C: ["A", "B", "D"],
    D: ["B", "C"]
}

const visited = [];
const visitedNode = [];

function dfs(startNode) {
    if (!visitedNode.includes(startNode)) {
        visited[startNode] = true;
        visitedNode.push(startNode);
    }

    for(let curNode of GRAPH[startNode]) {
        if(!visited[curNode]) {
            dfs(curNode);
        }
    }
}

dfs('A')
console.log(visitedNode);    // [ 'A', 'B', 'C', 'D' ]

 

 

dfs() 함수를 통해 얻은 방문한 순서 경로인 visitedNode를 출력한 결과 위의 탐색 과정의 탐색 경로와 동일한 것을 확인할 수 있었습니다. 위 처럼 깊이 너비 탐색(DFS)는 재귀함수를 활용하여 직관적으로 구현할 수 있습니다.

 

 

오늘은 탐색 알고리즘의 기본인 깊이 너비 탐색(DFS: Depth First Search) 알고리즘을 공부해보았습니다. 오늘도 함께 공부해주셔서 감사합니다.