DFS(깊이 우선 탐색)

DFS는 그래프의 한 정점에서 시작해, 가능한 한 깊게 탐색하다가 더 이상 갈 곳이 없으면 다시 이전 정점으로 되돌아가며 탐색을 이어가는 방식입니다.

스택 구조 (재귀 함수 또는 직접 스택 사용)를 기반으로 동작합니다.

DFS의 경우, 한 방향으로 가능한 깊이까지 탐색을 우선합니다. 즉, 하나의 가능한 경로를 재귀적으로 끝까지 따라가며 탐색하기 때문에 조건을 만족하는 해답이 그 경로 상에 있다면 매우 빠르게 도달할 수 있습니다.

보통 다음과 같은 문제에서 사용된다. 공통적으로 모든 경우를 탐색해야하는 경우 사용된다.

1. 모든 경로 탐색	시작 지점부터 도착 지점까지 갈 수 있는 모든 경로를 찾는 문제.
2. 백트래킹 문제	조합, 순열, N-Queen 등 조건을 만족하는 경우의 수 탐색
3. 연결 요소 세기	그래프에서 연결된 그룹(connected component)의 개수 세기
4. 미로 탐색	갈 수 있는 경로를 따라 깊게 탐색하며 길이 존재하는지 확인
5. 사이클 탐지	DFS 도중 방문한 노드를 또 만나면 사이클 존재 가능성
6. 섬의 개수 문제	2차원 배열에서 인접한 땅(1)을 DFS로 모두 탐색 후 섬 개수 카운팅

JavaScript로 구현: 인접 리스트 기반

const graph = [
  [],         // 0번 인덱스는 사용하지 않음
  [2, 3],     // 1번 노드와 연결된 노드들
  [4],
  [5, 6],
  [],
  [],
  []
];

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

function dfs(v) {
  visited[v] = true;
  console.log(v); // 방문 순서 출력

  for (const next of graph[v]) {
    if (!visited[next]) {
      dfs(next);
    }
  }
}

dfs(1); // 1번 노드부터 탐색 시작

//실행 결과
1
2
4
3
5
6

JavaScript로 구현: 인접 행렬 기반

const graph = [
  // 0번 인덱스는 사용하지 않음
  [0, 0, 0, 0, 0, 0, 0], // dummy
  [0, 0, 1, 1, 0, 0, 0], // 1번 노드 → 2, 3
  [0, 0, 0, 0, 1, 0, 0], // 2번 노드 → 4
  [0, 0, 0, 0, 0, 1, 1], // 3번 노드 → 5, 6
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0],
];

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

function dfs(v) {
  visited[v] = true;
  console.log(v); // 방문 순서 출력

  for (let i = 1; i < graph.length; i++) {
    if (graph[v][i] === 1 && !visited[i]) {
      dfs(i);
    }
  }
}

dfs(1);

// 실행 결과
1
2
4
3
5
6

Grid(격자) 기반 DFS

const dx = [0, 1];
const dy = [1, 0];

function inRange(x, y) {
  return 0 <= x && x < 5 && 0 <= y && y < 5;
}

function canGo(x, y) {
  if (!inRange(x, y)) return false;
  if (visited[x][y] || grid[x][y] === 0) return false;
  return true;
}

function dfs(x, y) {
  for (let i = 0; i < dx.length; i++) {
    const newX = x + dx[i];
    const newY = y + dy[i];

    if (canGo(newX, newY)) {
      visited[newY][newX] = true;
      answer[newY][newX] = order++;
      dfs(newX, newY);
    }
  }
}

// 초기화 예시
const visited = Array.from({ length: 5 }, () => Array(5).fill(false));
const answer = Array.from({ length: 5 }, () => Array(5).fill(0));
let order = 1;
visited[0][0] = 1;
answer[0][0] = order++;
dfs(0, 0);

주요 특징

구분	DFS 설명
탐색 방향	깊이 우선 (한 방향으로 최대한 진행 후, 백트래킹)
자료구조	스택 or 재귀
구현 난이도	간단 (재귀로 쉽게 구현 가능)
시간 복잡도	O(V + E)
활용 예시	미로 탐색, 백트래킹 문제, 사이클 탐지 등
방문 기록 방식	보통 visited[] 배열 사용

예상 면접 질문

DFS와 BFS의 차이점은?

• DFS는 깊이 우선, BFS는 너비 우선 탐색입니다.
• DFS는 스택(재귀) 기반, BFS는 큐 기반입니다.
• DFS는 특정 조건 만족 여부를 빨리 찾는 데 유리하고, BFS는 최단 경로를 구할 때 유리합니다.

DFS는 언제 사용하나요?

• 미로 탐색, 퍼즐, 조합 탐색, 백트래킹 문제 등 모든 경로를 탐색하거나 특정 조건을 만족하는 경로를 찾을 때 DFS가 유용합니다.