DFS, BFS

DFS(깊이 우선 탐색) & BFS(너비 우선 탐색)

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

개념

DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 최대한 깊이 내려간 후, 더 이상 갈 곳이 없으면 되돌아오는 방식으로 탐색함.

동작 과정

1. 시작 노드를 방문하고 스택에 넣음.
2. 현재 노드에서 방문하지 않은 인접 노드가 있으면 해당 노드를 방문하고 스택에 넣음.
3. 방문할 수 있는 모든 노드를 방문하면, 스택에서 노드를 하나씩 꺼내면서 탐색을 계속 진행함.
4. 스택이 비면 탐색이 종료됨.

구현 방법

• 스택(Stack) 또는 재귀(Recursion) 를 사용하여 구현할 수 있음.

코드 (Java)

import java.util.*;

public class DFSSample {
    static void dfs(List<List<Integer>> graph, boolean[] visited, int node) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(graph, visited, neighbor);
            }
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < 6; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(2).add(4);
        graph.get(2).add(5);

        boolean[] visited = new boolean[6];
        dfs(graph, visited, 1);
    }
}

시간 복잡도

• O(V + E) (V: 정점 수, E: 간선 수)
• 그래프의 모든 노드를 한 번씩 방문하기 때문

---

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

개념

BFS(Breadth-First Search)는 가까운 노드부터 탐색하는 방식으로, 큐(Queue)를 활용하여 구현함.

동작 과정

1. 시작 노드를 방문하고 큐에 넣음.
2. 큐에서 노드를 꺼내고, 방문하지 않은 인접 노드를 모두 큐에 넣음.
3. 큐가 비어 있을 때까지 위 과정을 반복함.

구현 방법

• 큐(Queue) 를 사용하여 구현함.

코드 (Java)

import java.util.*;

public class BFSSample {
    static void bfs(List<List<Integer>> graph, boolean[] visited, int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

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

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < 6; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(2).add(4);
        graph.get(2).add(5);

        boolean[] visited = new boolean[6];
        bfs(graph, visited, 1);
    }
}

시간 복잡도

• O(V + E) (V: 정점 수, E: 간선 수)
• 모든 노드를 방문하면서 탐색을 수행하기 때문

---

3. DFS vs BFS 비교

기준	DFS	BFS
탐색 방식	깊이 우선 (Depth-first)	너비 우선 (Breadth-first)
자료 구조	스택(Stack) or 재귀(Recursion)	큐(Queue)
속도	목표 노드가 깊은 곳에 있으면 빠름	목표 노드가 가까운 곳에 있으면 빠름
경로 탐색	모든 경로 탐색에 유리	최단 경로 탐색에 유리
공간 복잡도	O(V) (재귀 호출 스택 사용)	O(V) (큐에 노드 저장)

---

4. DFS와 BFS의 활용

DFS가 유리한 경우

• 모든 가능한 경로를 탐색해야 하는 경우 (예: 백트래킹 문제)
• 그래프가 깊고 가지가 적은 경우

BFS가 유리한 경우

• 최단 경로를 찾아야 하는 경우 (예: 미로 탐색, 최단 거리 문제)
• 그래프가 넓고 가지가 많은 경우

---

5. 결론

• DFS: 깊이 우선 탐색으로 모든 경우의 수를 조사할 때 유리함.
• BFS: 너비 우선 탐색으로 최단 경로를 찾을 때 유리함.
• 문제 유형에 따라 DFS와 BFS를 적절히 선택하여 사용해야 함.

 

 

 

 

출처 : ChatGPT