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

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

🔎 깊이 우선 탐색(DFS) 이란?

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
• 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
• 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

🔎 깊이 우선 탐색(DFS) 특징

• 자기 자신을 호출하는 순환 알고리즘(재귀)의 형태 를 가지고 있다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.

🔎 깊이 우선 탐색(DFS) 과정

1. a 노드(시작 노드)를 방문한다.
   ✓ 방문한 노드는 방문했다고 표시한다.
2. a와 인접한 노드들을 차례로 순회한다.
   ✓ a와 인접한 노드가 없다면 종료한다.
3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
   ✓ b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
   ✓ 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
   ✓ 아직 방문이 안 된 정점이 없으면 종료한다.
   ✓ 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

🔎 간단 코드 구현

2진수 출력

function solution(n) {
    let answer="";
    function DFS(n) {
        if (n === 0) return;
        else {
            DFS(parseInt(n/2))
            answer+=String(n % 2);
        } 
    }

    DFS(n);
    return answer;
}

console.log(solution(11));

🙏🏻 참조

• https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
• 자바스크립트 알고리즘 문제풀이 (https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard)