알고리즘

그래프 탐색 - DFS/BFS란?

1. DFS/BFS란 무엇인가?

DFS(Depth-First Search, 깊이 우선 탐색) 와 BFS(Breadth-First Search, 너비 우선 탐색) 는 그래프·트리에서 모든 정점을 빠짐없이 방문하기 위한 가장 기본적인 탐색 알고리즘이다.

둘 다 "아직 방문하지 않은 이웃으로 이동한다"는 큰 틀은 같지만, 다음 노드를 고르는 기준(탐색 순서) 이 다르다.

비교 항목DFS (깊이 우선)BFS (너비 우선)
탐색 방향한 경로를 끝까지 파고든 뒤 돌아옴시작점에서 가까운 정점부터 층(level) 단위로
자료구조스택(Stack) / 재귀 호출 스택큐(Queue)
대표 활용경로 존재, 사이클, 연결 요소, 위상 정렬최단 거리(가중치 없는 그래프), 레벨 탐색
직관"막다른 골목까지 갔다가 되돌아온다""물결처럼 퍼져 나간다"

왜 탐색 알고리즘이 중요한가?

대부분의 문제는 결국 "어떤 상태(노드)에서 다른 상태로 갈 수 있는가" 로 모델링된다.

  • 미로·격자 맵 → 상하좌우 이동 그래프
  • 소셜 네트워크 → 친구 관계 그래프
  • 웹 크롤링 → 페이지 링크 그래프
  • 상태 공간 문제(퍼즐, 게임) → 가능한 조작을 간선으로 둔 그래프

이 구조를 이해하면 DFS/BFS는 문제 해결의 기본 도구가 된다.


2. 그래프를 코드로 표현하는 방법

탐색을 구현하려면 먼저 그래프를 자료구조로 표현해야 한다.

① 인접 리스트 (Adjacency List)

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2],
};
  • 공간 복잡도: O(V+E)O(V + E) (VV: 정점 수, EE: 간선 수)
  • 희소 그래프(간선이 적은 경우)에 유리

② 인접 행렬 (Adjacency Matrix)

// matrix[i][j] === 1 이면 i → j 간선 존재
const matrix = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 1],
  [0, 1, 1, 0],
];
  • 공간 복잡도: O(V2)O(V^2)
  • 두 정점 연결 여부를 O(1)O(1)에 확인 가능, 밀집 그래프에 유리

3. DFS — 깊이 우선 탐색

동작 원리

  1. 시작 정점을 방문 처리한다.
  2. 인접한 미방문 정점 하나를 골라 즉시 이동한다.
  3. 더 이상 갈 곳이 없으면 이전 정점으로 되돌아간다. (백트래킹)
  4. 모든 정점을 방문할 때까지 반복한다.

스택(또는 재귀 호출 스택)에 "다음에 되돌아갈 위치"가 쌓이므로, 한 줄기를 깊게 파고드는 형태가 된다.


💻 예시 코드

재귀 방식 (가장 직관적)

const dfsRecursive = (graph, start) => {
  const visited = new Set();
  const order = [];

  const dfs = (node) => {
    visited.add(node);
    order.push(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        dfs(next);
      }
    }
  };

  dfs(start);
  return order;
};

스택 방식 (반복문)

const dfsIterative = (graph, start) => {
  const visited = new Set();
  const order = [];
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;

    visited.add(node);
    order.push(node);

    // 스택이므로 나중에 push한 이웃이 먼저 방문된다
    for (const next of [...(graph[node] ?? [])].reverse()) {
      if (!visited.has(next)) {
        stack.push(next);
      }
    }
  }

  return order;
};

DFS를 언제 쓰는가?

  • 경로의 존재 여부 확인 (A에서 B로 갈 수 있는가?)
  • 연결 요소(Connected Component) 개수 세기
  • 사이클 탐지 (유향/무향 그래프)
  • 백트래킹이 필요한 문제 (순열, 조합, N-Queen, 미로 경로 나열)
  • 위상 정렬, 그래프 사이클 기반 문제의 기반 탐색
  • 트리/그래프에서 모든 경로를 깊게 탐색해야 할 때

가중치가 없는 그래프의 최단 거리에는 DFS보다 BFS가 적합하다. DFS는 "먼저 도착한 경로"가 최단임을 보장하지 않는다.


4. BFS — 너비 우선 탐색

동작 원리

  1. 시작 정점을 큐에 넣고 방문 처리한다.
  2. 큐에서 정점을 하나 꺼낸다.
  3. 그 정점의 미방문 이웃을 모두 큐에 넣는다.
  4. 큐가 빌 때까지 반복한다.

같은 "거리(깊이)"에 있는 정점을 먼저 모두 방문한 뒤 다음 거리로 넘어가므로, 시작점에서 가까운 순으로 탐색한다.


💻 예시 코드

const bfs = (graph, start) => {
  const visited = new Set([start]);
  const order = [];
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift(); // 실제 코테에서는 인덱스 포인터나 deque 권장
    order.push(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
  }

  return order;
};

최단 거리까지 함께 구하기 (가중치 없는 그래프)

const bfsShortestPath = (graph, start) => {
  const dist = new Map([[start, 0]]);
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();

    for (const next of graph[node] ?? []) {
      if (!dist.has(next)) {
        dist.set(next, dist.get(node) + 1);
        queue.push(next);
      }
    }
  }

  return dist; // Map<node, 시작점으로부터의 최단 거리>
};

간선 가중치가 모두 1(또는 동일)일 때, BFS로 처음 도달한 거리가 곧 최단 거리다.


BFS를 언제 쓰는가?

  • 최단 경로 / 최소 이동 횟수 (미로 탈출, 숨바꼭질, 나이트 이동 등)
  • 레벨 단위 처리 (트리 레벨 순회, 촌수 계산)
  • 이분 그래프 판별
  • 상태가 전이되는 문제에서 "최소 조작 횟수" 를 구할 때

5. 시간 복잡도 · 공간 복잡도

인접 리스트 기준으로, DFS와 BFS의 점근 복잡도는 동일하다.

항목복잡도설명
시간 복잡도O(V+E)O(V + E)각 정점·각 간선을 상수 시간에 한 번씩 처리
공간 복잡도O(V)O(V)visited 배열/집합 + 스택·큐에 최대 O(V)O(V) 저장
인접 행렬 + 탐색O(V2)O(V^2)이웃 확인이 정점마다 O(V)O(V)라서 전체가 O(V2)O(V^2)

구현 시 주의할 공간 이슈

  • 재귀 DFS: 호출 스택 깊이가 O(V)O(V)까지 커질 수 있다. 정점이 매우 많으면 스택 오버플로우 위험이 있다 → 반복(스택) DFS를 고려한다.
  • JS에서 queue.shift(): 배열 앞 삭제가 O(N)O(N)이라 큰 입력에서 느려질 수 있다 → 인덱스로 front를 옮기거나 deque를 사용한다.

6. DFS vs BFS, 어떻게 고를까?

상황추천
가중치 없는 그래프의 최단 거리 / 최소 횟수BFS
경로 하나라도 있으면 됨 / 존재 여부만 확인DFS 또는 BFS
모든 경우의 수를 깊게 탐색 (백트래킹)DFS
연결 요소, 사이클, 위상 정렬 계열주로 DFS
레벨·촌수·층 단위 처리BFS
가중치가 있는 최단 경로Dijkstra / 0-1 BFS 등 (일반 BFS 아님)

한 줄 요약:

  • "가장 가까운 / 최소 횟수" → BFS
  • "깊게 파고들며 모든 가능성 탐색" → DFS

7. 격자(Grid)에서의 DFS/BFS

코테에서 가장 자주 나오는 형태는 2차원 맵이다. 상하좌우(또는 대각선)를 이웃으로 두면 그대로 그래프 탐색이 된다.

const dirs = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

const bfsGrid = (grid, sr, sc) => {
  const rows = grid.length;
  const cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
  const queue = [[sr, sc]];
  visited[sr][sc] = true;
  let steps = 0;

  while (queue.length > 0) {
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const [r, c] = queue.shift();

      // 목표 도달 조건을 여기에 두면 "최소 이동 횟수"가 된다
      // if (r === er && c === ec) return steps;

      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;

        if (
          nr < 0 ||
          nr >= rows ||
          nc < 0 ||
          nc >= cols ||
          visited[nr][nc] ||
          grid[nr][nc] === 0 // 벽 등
        ) {
          continue;
        }

        visited[nr][nc] = true;
        queue.push([nr, nc]);
      }
    }

    steps += 1;
  }

  return -1; // 도달 불가
};

8. 자주 하는 실수와 팁

실수

  1. visited를 늦게 표시 → 같은 노드가 큐/스택에 여러 번 들어가 시간 초과
  2. 무방향 그래프에서 양방향 간선을 빼먹음
  3. 시작점이 여러 개인 문제에서 큐에 시작점을 한 번에 넣지 않음 (다중 소스 BFS)
  4. DFS로 최단 거리를 구하려고 함

팁

  • 방문 처리는 큐/스택에 넣을 때 하는 편이 안전하다 (특히 BFS).
  • 문제를 읽자마자 "노드가 무엇인가? 간선이 무엇인가?" 를 먼저 정의한다.
  • 출력이 "최소 횟수"면 거의 항상 BFS 후보, "모든 경우의 수/경로 나열"이면 DFS·백트래킹 후보다.

9. 정리

키워드DFSBFS
자료구조Stack / RecursionQueue
탐색 순서깊이 우선너비(거리) 우선
복잡도O(V+E)O(V + E)O(V+E)O(V + E)
대표 강점백트래킹, 구조 분석최단 거리(비가중치)

DFS와 BFS는 서로 대체재가 아니라 목적에 따라 고르는 도구다.
그래프/격자/상태 공간으로 모델링만 되면, 두 알고리즘만으로도 상당히 많은 탐색 문제를 해결할 수 있다.