DFS (Depth-First Search)

DFS (Depth-First Search)

코딩 테스트에서의 DFS는 “상태를 하나 선택하고, 그 선택을 끝까지 밀고 가보는 탐색 패턴” 입니다.

그래프가 없어도 DFS 성립 가능

---

기본 형태

재귀 함수로 구현

핵심은 선택 → 탐색 → 복원

function dfs(state) {
  if (종료조건) {
    처리;
    return;
  }

  for (선택지) {
    선택;
    dfs(다음상태);
    선택취소;
  }
}

---

DFS 판별 기준

• 선택을 단계적으로 누적하는가?

  한 번에 답이 나오지 않고 선택 -> 다음 선택 구조

• 깊이(depth)가 의미 있는가?

  n번 선택해야했을 때, 끝에 도달했을 때 등 목표 깊이 존재

• 모든 경우를 봐야 하는가?

  모든 경우를 탐색, 가능한 경우의 수를 구하라 등

• 이전 상태로 돌아가야 하는가?

  선택을 취소하고 다른 선택을 해야함

---

DFS 유형

---

조합 DFS

몇 개를 고르는 문제

• i < j < k
• 순서 중요 ❌

삼총사 문제

function solution(number) {
  let count = 0;

  function dfs(start, depth, sum) {
    if (depth === 3) {
      if (sum === 0) count++;
      return;
    }

    for (let i = start; i < number.length; i++) {
      dfs(i + 1, depth + 1, sum + number[i]);
    }
  }

  dfs(0, 0, 0);
  return count;
}

---

순열 DFS

순서를 고려해 나열

• visited 배열
• 자리 채우기

function permute(nums) {
  const result = [];
  const visited = Array(nums.length).fill(false);

  function dfs(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (visited[i]) continue;

      visited[i] = true;
      path.push(nums[i]);
      dfs(path);
      path.pop();
      visited[i] = false;
    }
  }

  dfs([]);
  return result;
}

---

경로 탐색

이동하는 문제

• 상하좌우
• visited
• 도착 조건

function dfs(x, y) {
  if (도착) return true;

  for (방향) {
    if (갈 수 있으면) {
      dfs(nx, ny);
    }
  }
}

---

배치 DFS

위치를 정하는 문제

• 충돌 검사
• 행 / 열 / 대각

예: N-Queen