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

 

DFS, 깊이 우선 탐색

DFS란?

Depth-First Search의 약자이자 깊이 우선 탐색으로 부르며, Graph (그래프)에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 즉, 그래프의 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 간단하게는 시작 노드에서 출발하여, 한 방향으로 갈 수 있을 때까지 깊이 탐색한 뒤 더 이상 갈 수 없으면 직전에 방문했던 노드로 되돌아가 다른 경로를 탐색하는 방식이라고 할 수 있습니다.

 

출처 : https://developer-mac.tistory.com/64

 

특징

• 깊이 우선으로 진행 : 갈 수 있는 곳까지 재귀적으로(또는 스택을 사용하여) 끝까지 들어간 뒤, 더 이상 진행할 수 없으면 되돌아노는 방식
• 트리 구조나 그래프 모두 탐색 가능
• 방문 기록(visited 배열 등)을 사용하여 중복 방문을 방지
• 인접 리스트(Adjacency List)나 인접 행렬(Adjacency Matrix)로 그래프를 표현할 수 있음

 

활용 분야

• 위상 정렬(Topological Sort) : DAG(Directed Acyclic Graph)에서 위상 정렬을 할 때 DFS 기반으로 구현할 수 있음
• 사이클 검출(Cycle Detection) : 무방향/방향 그래프에서 사이클 존재 여부 확인 시 활용
• Connected Component(연결 요소) 탐색 : 그래프에서 연결 요소들을 탐색해 몇 개의 부분 집합이 존재하는지 찾는 데 사용
• 미로 찾기, 퍼즐 등 경로 탐색 : 2차원 맵, 미로 등에서 경로 유무 확인 시 DFS/백트래킹 활용
• 백트래킹(Backtracking) : 모든 경우의 수를 시도해볼 때 DFS를 확장하여 사용

 

---

DFS 구현

문제를 DFS로 해결하기 위해서는 대략 아래와 같은 과정이 필요합니다:

• 문제 상황을 그래프나 트리로 추상화
• 다시 코드로 표현
• DFS 구현

 

문제 상황을 그래프나 트리로 추상화

문제 상황을 그래프/트리로 추상화 하는 실제 예시는 아래와 같습니다:

• 미로 찾기 : 미로의 각 방(혹은 교차점)을 노드로 보고, 복도(길)을 간선으로 표현
• 지도 경로 찾기 : 도시를 노드로, 도시간 도로를 간선으로 표현
• 퍼즐(예: 8-puzzle) : 하나의 상태를 노드로 보고, 상태 변환(이동)을 간선으로 표현

즉, 문제 속 "객체들(요소들)과 그 연결 관계(상호작용, 이동, 의존 관계 등)를 노드와 간선으로 바꾸어 생각하는 과정입니다. 

 

 

이처럼, 문제에서 핵심이 되는 부분을 어떻게 노드와 간선으로 연결할지 파악하는 것이 1단계입니다.

 

인접 리스트(Adjacency List) 구성

그래프로 추상화가 끝났다면, 이를 코드에서 다룰 수 있는 자료구조로 만들어야 합니다. 주로 인접 리스트를 많이 사용합니다.

// 예시: 위 미로(그래프)를 인접 리스트로 표현
const graph = {
  0: [1, 3],
  1: [0, 2],
  2: [1, 4],
  3: [0, 4],
  4: [2, 3],
};

 

• 노드 0은 1, 3번 노드와 연결
• 노드 1은 0, 2번 노드와 연결
• ... (이하 동일)

 

다시 코드로 표현하기

그래프가 인접 리스트 형태로 표현되었다면, 이제 실제 코드 내에서 그래프를 다루는 방법을 마련해야 합니다.

 

문제를 풀지 전, "어떤 입력이 주어지면, 어떻게 그래프로 구성할 것인가?"를 코드로 작성합니다.

예: 사용자가 노드 개수와 간선 목록을 입력한다면,

// 가령 edges = [[0,1],[0,3],[1,2],[2,4],[3,4]] 형태라고 가정
function buildGraph(n, edges) {
  const graph = {};
  for (let i = 0; i < n; i++) {
    graph[i] = []; // 노드 i에 대한 리스트 초기화
  }
  // 양방향 그래프라고 가정
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }
  return graph;
}

// 사용 예시
const edges = [[0,1],[0,3],[1,2],[2,4],[3,4]];
const n = 5; // 노드 수 (0 ~ 4)
const graph2 = buildGraph(n, edges);
console.log(graph2);

 

이 과정을 통해, 문제에서 주어지는 정보 => 코드 상의 인접 리스트로 전환하게 됩니다.

 

DFS 구현

DFS(깊이 우선 탐색) 원리

DFS는 한 갈래로 깊숙이 파고든 뒤 더 이상 갈 수 없으면 되돌아와서 다른 경로를 탐색하는 방법입니다.

 

0 => 1 => 2 => 3 => 4 순서로 탐색할 수도 있고, 간선 구성이나 코드의 방문 순서에 따라 달라질 수 있지만, 공통적으로 "일단 깊이 들어간다"는 점이 핵심입니다.

 

재귀(Recursive) DFS 예시

function dfs(graph, start, visited = {}) {
  // 현재 노드를 방문 처리
  visited[start] = true;
  console.log("방문 노드:", start);

  // 인접 노드 탐색
  for (const next of graph[start]) {
    if (!visited[next]) {
      dfs(graph, next, visited);
    }
  }
}

// 사용 예시
dfs(graph, 0);

 

• `visited`는 노드 중복 방문을 방지하기 위한 객체(또는 배열)

스택(stack) 기반 DFS 예시

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

  while (stack.length > 0) {
    const node = stack.pop();
    console.log("방문 노드:", node);

	for (const next of graph[node]) {
        if (visited[next]) continue;
        // 방문하지 않은 인접 노드 push
        stack.push(next);
    }
  }
}

// 사용 예시
dfsStack(graph, 0);

 

• 재귀 대신 직접 stack을 만들어 DFS 접근을 구현한 모습입니다.
• 노드가 매우 많은 경우, 재귀 스택 오버플로우가 걱정될 때 이런 방식을 사용하기도 합니다.

 

 

 

 

Reference

• 1 [나를위한노트] | [코딩테스트 대비] DFS, BFS 정리