BFS & DFS

이번에는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자.
이 두 가지 탐색 방법은 그래프나 트리 구조에서 데이터를 탐색하거나 순회할 때 자주 사용되는 기본 알고리즘이다.

너비 우선 탐색(BFS)

너비 우선 탐색은 주로 그래프나 트리에서 최단 경로를 찾거나, 특정 레벨에 있는 노드들을 탐색할 때 사용된다.
BFS는 먼저 시작 노드에서 가까운 노드들을 차례로 탐색하며, 큐(queue)를 사용하여 구현된다.

BFS의 동작 원리

BFS는 다음과 같은 단계로 동작한다:

시작 노드를 큐에 삽입하고, 방문 표시를 한다.
큐에서 노드를 하나씩 꺼내 해당 노드와 인접한 모든 노드를 탐색한다.
아직 방문하지 않은 인접 노드를 큐에 삽입하고, 방문 표시를 한다.
큐가 빌 때까지 2번과 3번 과정을 반복한다.

BFS의 시간 복잡도

BFS의 시간 복잡도는 O(V + E)이다. 여기서 V는 노드의 수, E는 간선의 수를 의미한다.
BFS는 노드와 간선의 개수에 비례하여 시간이 소요된다.

BFS 예제 코드

아래는 BFS를 구현한 간단한 예제 코드이다.
이 코드에서는 그래프에서 특정 노드를 시작으로 너비 우선 탐색을 수행한다.

import java.util.*;

public class BFSExample {

    public static void bfs(int startNode, Map<Integer, List<Integer>> graph) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(startNode);
        visited.add(startNode);

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

            for (int neighbor : graph.get(currentNode)) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3, 4));
        graph.put(2, Arrays.asList(5, 6));
        graph.put(3, Arrays.asList(7, 8));
        graph.put(4, Arrays.asList(9));
        graph.put(5, new ArrayList<>());
        graph.put(6, new ArrayList<>());
        graph.put(7, new ArrayList<>());
        graph.put(8, new ArrayList<>());
        graph.put(9, new ArrayList<>());

        bfs(1, graph);  // 출력: 1 2 3 4 5 6 7 8 9
    }
}

깊이 우선 탐색(DFS)

깊이 우선 탐색은 가능한 깊은 노드까지 탐색을 진행한 후, 더 이상 갈 수 없는 경우 다시 이전 노드로 돌아가는 방식으로 탐색을 진행한다.
DFS는 주로 재귀를 통해 구현되며, 백트래킹(backtracking) 문제 해결에 자주 사용된다.

DFS의 동작 원리

DFS는 다음과 같은 단계로 동작한다:

시작 노드를 방문하고, 방문 표시를 한다.
현재 노드에서 방문하지 않은 인접 노드가 있으면, 그 노드를 따라가 탐색을 계속한다.
더 이상 방문할 노드가 없으면, 이전 노드로 돌아가면서 탐색을 이어나간다.
모든 노드를 방문할 때까지 과정을 반복한다.

DFS의 시간 복잡도

DFS의 시간 복잡도 역시 O(V + E)이다.
노드와 간선을 모두 탐색하기 때문에 BFS와 동일한 시간 복잡도를 가진다.

DFS 예제 코드

아래는 DFS를 재귀적으로 구현한 간단한 예제 코드이다.
이 코드에서는 그래프에서 특정 노드를 시작으로 깊이 우선 탐색을 수행한다.

import java.util.*;

public class DFSExample {

    public static void dfs(int currentNode, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
        visited.add(currentNode);
        System.out.print(currentNode + " ");

        for (int neighbor : graph.get(currentNode)) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, graph, visited);
            }
        }
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3, 4));
        graph.put(2, Arrays.asList(5, 6));
        graph.put(3, Arrays.asList(7, 8));
        graph.put(4, Arrays.asList(9));
        graph.put(5, new ArrayList<>());
        graph.put(6, new ArrayList<>());
        graph.put(7, new ArrayList<>());
        graph.put(8, new ArrayList<>());
        graph.put(9, new ArrayList<>());

        Set<Integer> visited = new HashSet<>();
        dfs(1, graph, visited);  // 출력: 1 2 5 6 3 7 8 4 9
    }
}

BFS & DFS의 사용 사례

경로 탐색
BFS는 최단 경로를 찾는 문제에 자주 사용되며, DFS는 특정 경로를 찾거나 모든 가능한 경로를 탐색해야 하는 문제에 유용하다.
그래프 순회
BFS와 DFS는 그래프 순회에서 각각 다른 방식으로 그래프를 탐색하므로, 문제의 특성에 따라 적합한 방법을 선택할 수 있다.
백트래킹
DFS는 백트래킹 알고리즘의 핵심으로, 가능한 모든 해결책을 탐색하는데 사용된다.
예를 들어, 퍼즐 문제나 조합 문제에서 활용된다.

BFS와 DFS 선택 기준

탐색 목적
최단 경로를 찾고자 한다면 BFS를, 모든 경로를 탐색하거나 특정 깊이까지 탐색하고자 한다면 DFS를 사용하는 것이 좋다.
메모리 사용
BFS는 큐에 모든 노드를 저장해야 하므로 메모리 사용이 많다.
반면 DFS는 재귀 호출을 사용하므로 상대적으로 적은 메모리를 사용한다.

BFS와 DFS는 모두 중요한 탐색 알고리즘이며, 상황에 맞게 잘 선택하고 활용하면 효율적으로 문제를 해결할 수 있을 것이다.
이 글을 통해 BFS와 DFS에 대해 더 깊이 이해할 수 있기를 바란다.