알고리즘, Tree, DFS

 

깊이 우선 탐색(Depth-First Search, DFS)은 그래프 또는 트리의 노드를 탐색하는 방법 중 하나로, 가능한 한 깊이 있는 노드를 우선으로 탐색합니다. DFS는 스택(stack) 자료 구조를 사용하여 구현할 수 있으며, 재귀적으로도 쉽게 구현할 수 있습니다.

DFS의 특징

1. 깊이 우선 탐색: 가능한 한 깊이 있는 노드를 먼저 탐색하고, 더 이상 깊이 갈 수 없을 때 다음 인접한 노드로 이동합니다.
2. 스택 사용: DFS는 LIFO(Last In, First Out) 특성을 가진 스택을 사용하여 다음에 탐색할 노드를 관리합니다. 재귀적 구현에서는 함수 호출 스택을 사용합니다.
3. 경로 탐색: 그래프나 트리에서 경로를 탐색할 때 유용하며, 모든 경로를 탐색하는 문제에 적합합니다.

DFS의 구현 (자바스크립트 예제)

트리에서의 DFS 구현 (재귀 사용)

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    let newNode = new Node(value);

    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let current = this.root;

    while (true) {
      if (value === current.value) return undefined;

      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else if (value > current.value) {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  find(value) {
    if (!this.root) return false;

    let current = this.root;
    let found = false;

    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        return true;
      }
    }

    return false;
  }

  DFS() {
    // Create a variable to store the values of nodes visited
    // Store the root of the BST in a variable called current
    // Write a helper function which accepts a node
    // Push the value of the node to the variable that stores the values
    // If the node has a left property, call the helper function with the left property on the node
    // If the node has a right property, call the helper function with the right property on the node
    // Invoke the helper function with the current variable
    // Return the array of values

    let visited = [];
    let currentNode = this.root;

    function preorder(node) {
      visited.push(node.value);

      if (node.left) preorder(node.left);
      if (node.right) preorder(node.right);
    }

    preorder(currentNode);

    return visited;
  }
}

let tree = new BinarySearchTree();

console.log('tree is:', tree);
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(17);
tree.insert(7);
tree.insert(3);
tree.insert(13);
console.log('tree is:', tree);

console.log(tree.find(13));
console.log(tree.find(19));

console.log('DFS:', tree.DFS());

DFS의 동작 원리

1. 시작 노드에서 출발: DFS는 시작 노드에서 출발하여 깊이 있는 노드를 먼저 탐색합니다.
2. 재귀적 또는 반복적 접근: 재귀적으로 함수 호출을 통해 깊이 있는 노드를 탐색하거나, 스택을 사용하여 반복적으로 노드를 탐색합니다.
3. 방문 표시: 각 노드는 방문되면 방문 표시를 합니다.
4. 백트래킹: 더 이상 깊이 갈 수 없는 경우, 이전 노드로 되돌아가서 다른 경로를 탐색합니다.

DFS의 시간 복잡도

DFS의 시간 복잡도는 그래프의 노드 수(V)와 엣지 수(E)에 따라 O(V + E)입니다. 이는 모든 노드와 엣지를 한 번씩 방문하기 때문입니다. 트리의 경우 노드 수가 n일 때, 시간 복잡도는 O(n)입니다.

DFS는 경로 탐색, 사이클 탐지, 강력 연결 요소 찾기 등 다양한 문제에 유용하게 사용됩니다. 또한, 그래프의 모든 노드를 방문해야 하는 문제에 적합합니다.