[JavaScript] 깊이 우선 탐색, DFS(Depth-First Search)

DFS, Depth-First Search라고 불리는 이 깊이 우선 탐색은 대표적으로 많이 사용되는 알고리즘 중 하나 입니다.
이 글에서는 어떤 상황에서 BFS를 사용하며, 어떤 코드에서 사용되고 있는 지 알아보도록 하겠습니다.

---

깊이 우선 탐색(DFS)란 무엇일까?

깊이 우선 탐색(Depth-First Search)은 그래프나 트리와 같은 자료 구조에서 노드를 탐색하는 알고리즘 중 하나입니다. 

DFS는 시작 노드에서 출발하여 깊이를 우선으로 하여 노드들을 방문하는 방식으로, 

한 경로의 최대 깊이까지 도달한 후 다시 이전 노드로 돌아와 미방문 인접 노드를 방문하는 방식으로 진행됩니다.

DFS는 다음과 같은 순서로 실행됩니다

1. 시작 노드를 방문합니다.
2. 방문한 노드를 기준으로 인접한 미방문 노드가 있으면 그 노드로 이동하고, 방문처리합니다. 이 과정을 반복합니다.
3. 인접한 모든 노드를 방문한 후, 이전 노드로 돌아와서 다른 미방문 인접 노드를 찾아 방문합니다.
4. 모든 노드를 방문할 때까지 이 과정을 반복합니다.

---

DFS가 사용되는 상황은 언제일까?

DFS(깊이 우선 탐색)는 다양한 상황에서 사용됩니다. 주요 사용 사례는 다음과 같습니다

1. 연결 요소 찾기
   • 그래프에서 서로 연결된 구성 요소를 찾는 데 사용됩니다.
   • 이를 통해 서로 독립적인 그룹이나 클러스터를 식별할 수 있습니다.
2. 사이클 검출
   • 그래프에서 사이클 존재 여부를 확인하는 데 사용됩니다.
   • 사이클은 그래프에서 노드가 자기 자신으로 다시 돌아오는 경로를 의미합니다.
3. 경로 찾기 문제
   • 그래프에서 두 노드 간의 경로를 찾는 데 사용됩니다.
   • 이 경우, DFS는 경로를 찾거나 가능한 모든 경로를 찾는 데 사용할 수 있습니다.
4. 백트래킹 알고리즘
   • 퍼즐 문제, 스도쿠, N-퀸 문제 등의 백트래킹 기반 알고리즘에서 DFS는 가능한 해를 찾거나 모든 해를 찾는 데 사용됩니다.
5. 트리나 그래프의 깊이 계산
   • 특정 노드로부터 최대 깊이를 계산하는 데 사용됩니다.
   • 이 정보는 트리 밸런싱이나 성능 최적화와 같은 문제를 해결하는 데 도움이 됩니다.
6. 최적화 문제
   • 탐욕 알고리즘과 함께 사용되어 최적해를 찾는데 도움이 됩니다.
   • 이 경우, DFS는 탐색 공간을 줄이고, 탐욕 알고리즘이 더 빠르게 수렴하도록 합니다.

---

DFS 예제 코드들

1. 재귀를 사용한 DFS 구현

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

const visited = new Set();  // 방문한 노드를 저장할 Set

function dfsRecursive(graph, node) {
  if (!visited.has(node)) {
    console.log(node);
    visited.add(node);
    // 인접한 모든 노드에 대해 재귀 호출
    for (const neighbor of graph[node]) {
      dfsRecursive(graph, neighbor);
    }
  }
}

dfsRecursive(graph, 'A');

 

2. 스택을 사용한 DFS 구현

function dfsStack(graph, start) {
  const visited = new Set();
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();
    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);
      // 인접한 미방문 노드를 스택에 추가
      for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

dfsStack(graph, 'A');

 

3. 인접 행렬을 사용한 DFS 구현

const matrix = [
  [0, 1, 1, 0, 0, 0],
  [1, 0, 0, 1, 1, 0],
  [1, 0, 0, 0, 0, 1],
  [0, 1, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 1],
  [0, 0, 1, 0, 1, 0]
];

const visited = Array(matrix.length).fill(false);

function dfsMatrix(matrix, node) {
  if (!visited[node]) {
    console.log(node);
    visited[node] = true;
    // 인접한 모든 노드에 대해 깊이 우선 탐색 수행
    for (let neighbor = 0; neighbor < matrix[node].length; neighbor++) {
      if (matrix[node][neighbor] && !visited[neighbor]) {
        dfsMatrix(matrix, neighbor);
      }
    }
  }
}

dfsMatrix(matrix, 0);

---

End