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

깊이 우선 탐색 DFS란?

- 트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘

- 깊이를 우선시하여 모든 경우의 수를 탐색하기 때문에, 완전탐색 알고리즘에 속하기는 하지만, 항상 완전탐색으로는 사용되지 않음

- DFS는 주로 반복문을 활용하거나 재귀문을 통하여 구현

- ex) 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것

 

 

1. 시작 노드에 방문한다. (무한 루프를 돌지 않기 위해 방문 여부 체크 필수!)

2. 시작 노드와 인접한 노드 중 하나를 방문하여 인접 노드를 시작 노드로 다시 DFS를 진행한다. (방문 여부 체크)

3. 시작 노드가 없을 경우 재귀를 종료한다.

 

 

DFS 구현

// 그래프를 인접 리스트로 표현
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

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

function dfs(node) {
  if (visited.has(node)) return;

  console.log(node); // 방문 시 출력
  visited.add(node); // 방문 처리

  for (const neighbor of graph[node]) {
    dfs(neighbor);
  }
}

// A부터 DFS 시작
dfs('A');


//출력 결과
A
B
D
E
F
C

 

 

DFS (Depth-First Search)의 장단점

장점

1. 구현이 간단한 편이다.
   • 재귀 함수나 스택 자료구조만으로 쉽게 구현할 수 있다.
2. 공간을 적게 쓸 수 있다 (일반적인 경우)
   • BFS는 큐에 많은 노드를 저장해야 할 수 있는데, DFS는 경로 하나만 따라가므로 메모리 사용이 상대적으로 적다.
   • 단, 깊이가 매우 깊어지면 오히려 비효율적일 수 있음.
3. 모든 경로를 탐색하는 데 유리하다
   • 특정 조건을 만족하는 모든 해를 찾거나, 경로의 수를 구하는 문제에 적합하다.
   • 예: 미로 탈출 경로 모두 찾기, 백트래킹 기반 퍼즐 문제 등
4. 백트래킹에 활용하기 좋다
   • 상태를 쌓았다가 되돌리는 방식이 DFS의 흐름과 잘 맞아, 백트래킹 문제에 자주 쓰인다.

---

단점

1. 최단 경로를 보장하지 않는다
   • 가장 먼저 도착한 경로가 최단 경로가 아닐 수 있어서, 거리나 최소 이동 횟수가 중요한 문제엔 부적합하다.
   • → 이런 경우에는 BFS가 더 적합함.
2. 무한 루프 가능성
   • 방문 처리를 제대로 하지 않으면, 순환 구조(cycle)가 있는 그래프에서 무한히 돌 수 있다.
   • → visited 처리가 필수!
3. 재귀 호출로 인한 스택 오버플로우 위험
   • 재귀로 구현했을 때, 탐색 깊이가 너무 깊으면 스택 오버플로우가 발생할 수 있다.
   • → 반복문 + 명시적 스택으로 구현하면 방지 가능
4. 해가 깊은 곳에 있을 경우 시간이 오래 걸릴 수 있다
   • 해답이 얕은 곳에 있어도 깊은 경로를 먼저 탐색하다 보면, 불필요한 탐색이 많아질 수 있다.

 

DFS 코딩테스트 예제

예제1. 타겟 넘버

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

문제 설명

- 정수로 이루어진 배열 numbers가 주어집니다.

- 배열의 숫자들에 + 또는 -를 앞에 붙여 모두 더했을 때, 그 합이 target이 되는 경우의 수를 구하시오.

 

DFS 사용 이유

- 모든 경우(+, -를 붙이는)를 탐색해야 하므로 완전 탐색 + 백트래킹으로 DFS가 적합하다.

 

function solution(numbers, target) {
  let count = 0;

  function dfs(index, sum) {
    if (index === numbers.length) {
      if (sum === target) count++;
      return;
    }

    dfs(index + 1, sum + numbers[index]);
    dfs(index + 1, sum - numbers[index]);
  }

  dfs(0, 0);
  return count;
}

 

 

예제2. 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

문제 설명

- 컴퓨터 간 연결 상태가 담긴 adjacency matrix가 주어짐. 총 몇개의 네트워크(= 연결된 덩어리)가 있는지 구하는 문제.

 

DFS 사용 이유

- 한 컴퓨터와 연결된 모든 컴퓨터를 찾을 때 DFS로 깊이 들어가며 방문 처리하는 방식이 적합하다.

 

function solution(n, computers) {
  const visited = Array(n).fill(false);
  let count = 0;

  function dfs(node) {
    visited[node] = true;
    for (let i = 0; i < n; i++) {
      if (computers[node][i] === 1 && !visited[i]) {
        dfs(i);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i);
      count++;
    }
  }

  return count;
}