[알고리즘] BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)

그래프 탐색은 데이터를 구조화하고 처리하는 데 필수적인 알고리즘이다.

그중 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 가장 널리 사용되는 그래프 탐색 기법이다.

---

1. BFS와 DFS란?

 

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

•  그래프를 탐색할 때 가까운 노드부터 차례대로 방문하는 방식
• 큐(Queue)를 사용하여 구현

 

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

• 그래프를 탐색할 때 깊은 경로를 우선적으로 탐색하는 방식
• 스택(Stack)이나 재귀를 사용하여 구현

---

2.BFS와 DFS의 동작 원리

BFS의 동작 원리

1. 시작 노드를 큐에 추가하고 방문 처리한다.

2. 큐에서 노드를 하나 꺼내고, 해당 노드에 연결된 모든 인접 노드를 큐에 추가하여 방문 처리한다.

3. 큐가 빌 때까지 2번 과정을 반복한다.

 

 

BFS의 예제

import java.util.*;

public class BFSExample {
    public static void bfs(int start, List<List<Integer>> graph) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.size()];
        
        queue.offer(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " "); // 방문 노드 출력
            
            for (int next : graph.get(node)) {
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        graph.add(Arrays.asList()); // 노드 0은 사용하지 않음
        graph.add(Arrays.asList(2, 3, 8)); // 1번 노드와 연결된 노드들
        graph.add(Arrays.asList(1, 7));
        graph.add(Arrays.asList(1, 4, 5));
        graph.add(Arrays.asList(3, 5));
        graph.add(Arrays.asList(3, 4));
        graph.add(Arrays.asList(7));
        graph.add(Arrays.asList(2, 6, 8));
        graph.add(Arrays.asList(1, 7));

        bfs(1, graph); // 1번 노드부터 탐색
    }
}

 

 

 

DFS의 동작 원리

1. 시작 노드를 스택에 추가하고 방문 처리한다.

2. 스택의 최상단 노드에 인접한 방문하지 않은 노드를 스택에 추가하여 방문 처리한다.

3. 방문할 노드가 없으면 스택에서 제거하고, 다시 2번 과정을 반복한다.

4. 스택이 빌 때까지 탐색을 진행한다.

 

 

DFS의 예제(재귀 방식)

import java.util.*;

public class DFSExample {
    public static void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
        visited[node] = true;
        System.out.print(node + " "); // 방문 노드 출력
        
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                dfs(next, graph, visited);
            }
        }
    }
    
    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        graph.add(Arrays.asList()); // 노드 0은 사용하지 않음
        graph.add(Arrays.asList(2, 3, 8)); // 1번 노드와 연결된 노드들
        graph.add(Arrays.asList(1, 7));
        graph.add(Arrays.asList(1, 4, 5));
        graph.add(Arrays.asList(3, 5));
        graph.add(Arrays.asList(3, 4));
        graph.add(Arrays.asList(7));
        graph.add(Arrays.asList(2, 6, 8));
        graph.add(Arrays.asList(1, 7));

        boolean[] visited = new boolean[graph.size()];
        dfs(1, graph, visited); // 1번 노드부터 탐색
    }
}

 

---

4. BFS와 DFS의 비교

구분	BFS(너비 우선 탐색)	DFS(깊이 우선 탐색)
탐색 순서	가까운 노드부터 탐색	깊은 노드부터 탐색
자료구조	큐(Queue)	스택(Stack) 또는 재귀(Recursion)
시간 복잡도	O(V + E) (노드+간선 개수에 비례)	O(V + E) (노드+간선 개수에 비례)
활용 사례	최단 경로 탐색	모든 경로 탐색(백트래킹 등)

 

---

5. BFS와 DFS의 활용 예시

• BFS
  - 최단 경로 탐색: 두 노드 간의 최소 이동 거리를 구할 때
  - 그래프의 연결 여부 판단: 연결된 모든 노드를 탐색
• DFS
  - 백트래킹: 경로를 추적하며 모든 경우를 탐색
  - 사이클 탐지: 그래프 내에  순환 구조가 있는지 확인

---

결론

BFS는 최단 경로 탐색과 같은 너비 우선 문제에 적합하며, DFS는 백트래킹과 같이 깊이를 우선적으로 탐색하는 문제에 적합하다.

문제의 특성과 요구 사항에 따라 두 알고리즘 중 적절한 것을 선택하여 사용해야 한다.