깊이 우선 탐색 (DFS: Depth-First Search) 설명과 JavaScript 예제

깊이 우선 탐색(DFS)은 그래프나 트리 구조에서 가능한 한 깊이 내려간 뒤, 더 이상 갈 수 없으면 되돌아가는 방식의 탐색 알고리즘입니다. 재귀(Recursive) 또는 스택(Stack)을 사용해 구현할 수 있으며, 경로 탐색, 백트래킹 등 다양한 문제 해결에 활용됩니다.

---

1. 동작 원리

1. 시작 노드에서 방문 처리 후 인접 노드를 탐색
2. 방문하지 않은 인접 노드가 있다면 그 노드로 이동
3. 더 이상 방문할 곳이 없다면 이전 단계로 되돌아감 (백트래킹)
4. 모든 노드를 방문할 때까지 반복

---

2. DFS의 구현 방식

• 재귀 기반 DFS: 함수 호출 스택을 이용하여 구현
• 반복문 + 명시적 스택 사용: 스택 구조를 코드로 직접 구성

---

3. JavaScript 예제 (재귀 기반)

function dfsRecursive(graph, start, visited = new Set()) {
  console.log(start);
  visited.add(start);

  for (let neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited);
    }
  }
}

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

dfsRecursive(graph, 'A');

---

4. JavaScript 예제 (스택 기반)

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

  while (stack.length > 0) {
    const node = stack.pop();
    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);
      for (let neighbor of [...graph[node]].reverse()) {
        stack.push(neighbor);
      }
    }
  }
}

dfsStack(graph, 'A');

• 스택 기반 DFS는 스택을 직접 관리하며 순서를 제어할 수 있음
• reverse()는 방문 순서를 재귀 DFS와 맞추기 위한 처리

---

5. DFS의 특징

• 구현이 간단하고 직관적
• 경로 탐색, 순열/조합 생성, 백트래킹 문제에 적합
• 무한 루프 방지를 위해 반드시 방문 체크 필요

---

6. 시간 복잡도

그래프 유형	시간 복잡도
인접 리스트	O(V + E)
인접 행렬	O(V²)

• V: 노드 수, E: 간선 수

---

마무리

깊이 우선 탐색은 알고리즘 문제에서 자주 등장하는 기초 탐색 기법입니다. 특히 백트래킹, 미로 찾기, 그래프의 연결성 검사 등 다양한 문제에서 DFS를 활용할 수 있으며, 재귀 또는 스택 방식에 익숙해지는 것이 중요합니다.

DFS는 단순 탐색을 넘어 다양한 문제 해결 전략의 기초가 되는 알고리즘입니다.