[알고리즘] DFS vs BFS : 차이점 및 언제 사용해야 할까?

[알고리즘] DFS vs BFS: 차이점 및 언제 사용해야 할까?

1. DFS와 BFS란?

DFS(Depth-First Search)와 BFS(Breadth-First Search)는

그래프(또는 트리) 탐색 알고리즘입니다.

이 두 알고리즘은 자료구조 문제에서

경로 탐색,

연결 요소 찾기,

최단 거리 구하기 등 다양한 문제에 활용됩니다.

 

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

DFS는 한 방향으로 끝까지 탐색한 뒤,

더 이상 갈 곳이 없을 때 이전으로 돌아가며 탐색을 이어갑니다.

**스택(Stack)** 또는 **재귀(Recursion)** 를 활용합니다.

✔ DFS 예제 (재귀 방식)

public class DFSExample {
    static boolean[] visited = new boolean[6];
    static int[][] graph = {
        {},         // 0 (사용하지 않음)
        {2, 3},     // 1
        {4},        // 2
        {5},        // 3
        {},         // 4
        {}          // 5
    };

    public static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int next : graph[node]) {
            if (!visited[next]) dfs(next);
        }
    }

    public static void main(String[] args) {
        dfs(1); // 출력: 1 2 4 3 5
    }
}

✅ 특징:

- 재귀 또는 스택 사용

- 백트래킹(Backtracking) 문제에서 자주 사용

- 미로 찾기, 조합/순열 생성 문제에 유리 

3. BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 현재 노드의 이웃 노드부터 먼저 탐색 한 후,

그 이웃들의 이웃을 탐색합니다.

큐(Queue) 자료구조를 사용하며, 최단 거리 문제에서 자주 활용됩니다.

✔ BFS 예제 (큐 사용)

import java.util.*;

public class BFSExample {
    static boolean[] visited = new boolean[6];
    static int[][] graph = {
        {},         // 0 (사용하지 않음)
        {2, 3},     // 1
        {4},        // 2
        {5},        // 3
        {},         // 4
        {}          // 5
    };

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int next : graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        bfs(1); // 출력: 1 2 3 4 5
    }
}

✅ 특징:

- 큐를 사용하여 너비 우선으로 탐색

- 최단 거리 탐색, 최적 경로 탐색 문제에 효과적

- 미로 탈출, 게임 판 탐색 문제에 자주 사용 

4. DFS vs BFS 비교

항목	DFS	BFS
탐색 방식	깊이 우선	너비 우선
사용 자료구조	스택(또는 재귀)	큐(Queue)
주요 활용	백트래킹, 순열/조합, 경로 탐색	최단 거리, 최적 경로
메모리 사용	일반적으로 적음	넓게 탐색하므로 더 큼
종료 조건	끝까지 내려가며 탐색	가까운 노드부터 차례로 탐색

 

5. 언제 DFS를, 언제 BFS를 쓸까?

• ✔ DFS는 완전 탐색, 조합/순열 문제, 백트래킹에 적합
• ✔ BFS는 최단 거리, 레벨 기반 탐색에 적합
• ✔ DFS는 메모리를 적게 사용, BFS는 탐색 순서가 명확

 

📌 정리

• ✔ DFS와 BFS는 그래프/트리 탐색의 대표 알고리즘
• ✔ DFS는 깊이 우선, BFS는 너비 우선으로 탐색
• ✔ 각각의 특성을 이해하고 문제 유형에 따라 적절히 선택해야 함

---

🔗 다른 알고리즘 관련 글도 함께 확인해보세요!

알고리즘 문제 해결 전략: 재귀 함수와 백트래킹 정리