DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 비교(차이점, 장단점, 예시코드, 활용도)

2024.12.19 - [알고리즘] - DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도

DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도

2024.12.19 - [알고리즘] - BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복잡도

BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복잡도

 

 

DFS와 BFS 비교

 

 

 

 

dfs, bfs에 대한 설명을 먼저 보고 오시면 더욱 이해하기 좋습니다.

 

 

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프나 트리를 탐색하는 대표적인 알고리즘으로, 문제의 특성과 요구사항에 따라 적합한 방식을 선택하는 것이 중요합니다. 이 글에서는 DFS와 BFS의 개념, 유사점과 차이점, 시간 복잡도, 사용 분야, 그리고 각 알고리즘의 장단점을 비교하여 설명하겠습니다.

---

1. DFS와 BFS의 개념

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

DFS는 그래프의 한 경로를 끝까지 탐색한 후, 더 이상 탐색할 노드가 없으면 이전 경로로 되돌아가는 방식으로 동작합니다. 스택(Stack) 자료구조나 재귀를 기반으로 구현됩니다.

 

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

BFS는 시작 정점에서 가까운 노드부터 순차적으로 탐색하며, 모든 인접한 노드를 탐색한 후 다음 깊이로 이동합니다. 큐(Queue) 자료구조를 기반으로 구현됩니다.

---

반응형

2. DFS와 BFS의 유사점

1. 그래프 탐색: 둘 다 그래프의 모든 정점을 탐색하기 위한 알고리즘입니다.
2. 시간 복잡도: 일반적으로 두 알고리즘 모두 O(V + E)의 시간 복잡도를 가집니다.
   • V: 정점(Vertex)의 수
   • E: 간선(Edge)의 수
3. 방문 처리 필요: 순환 그래프에서는 방문 여부를 기록해야 무한 루프를 방지할 수 있습니다.
4. 다양한 문제 해결: 경로 탐색, 연결 요소 확인 등 그래프 관련 문제 해결에 사용됩니다.

 

3. DFS와 BFS의 차이점

구분	DFS	BFS
탐색 방식	한 경로를 끝까지 탐색한 후 백트래킹	가까운 정점부터 순차적으로 탐색
자료구조	스택(Stack) 또는 재귀(Recursion)	큐(Queue)
구현 난이도	재귀 호출을 사용하는 경우 간단	큐를 명시적으로 관리해야 하므로 복잡
메모리 사용	그래프가 넓은 경우 메모리 사용량이 적음	그래프가 깊은 경우 메모리 사용량이 적음
최단 경로 보장	보장하지 않음	무가중 그래프에서 최단 경로 보장
적용 문제	백트래킹, 퍼즐 문제, 강한 연결 요소 찾기	최단 경로, 레벨별 탐색, 네트워크 흐름 분석

 

 

4. 시간 복잡도 비교

두 알고리즘의 시간 복잡도는 동일하게 O(V + E) 입니다. 하지만 실제 성능은 그래프의 형태나 문제의 특성에 따라 달라질 수 있습니다.

1. DFS: 특정 경로 탐색이 필요한 문제에서 빠르게 동작합니다.
2. BFS: 최단 경로를 보장해야 하는 문제에 적합합니다.

---

 

5. 사용 분야

DFS의 주요 사용 분야

• 백트래킹 문제: 미로 탐색, N-Queen 문제
• 강한 연결 요소 찾기: 그래프의 특정 부분을 분리하거나 분석
• 트리의 순회: 전위, 중위, 후위 순회

BFS의 주요 사용 분야

• 최단 경로 문제: 무가중 그래프에서 최단 경로 탐색
• 레벨 탐색: 그래프의 레벨별 노드 탐색
• 네트워크 분석: 연결된 컴포넌트 찾기

---

 

6. DFS와 BFS의 장단점

DFS의 장단점

장점:

1. 백트래킹 문제에 적합
2. 그래프가 넓은 경우 메모리 사용 효율적
3. 구현이 간단(재귀 사용 시)

단점:

1. 최단 경로를 보장하지 않음
2. 순환 그래프에서 방문 처리 누락 시 무한 루프 발생 가능

 

BFS의 장단점

장점:

1. 무가중 그래프에서 최단 경로를 보장
2. 그래프의 레벨별 탐색 가능

단점:

1. 큐 사용으로 인해 메모리 사용량 증가 가능
2. 구현이 비교적 복잡

---

 

7. 예제 코드 비교

C 언어 예제

DFS

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

int graph[MAX][MAX];
bool visited[MAX];

void dfs(int v, int n) {
    visited[v] = true;
    printf("%d ", v);

    for (int i = 0; i < n; i++) {
        if (graph[v][i] == 1 && !visited[i]) {
            dfs(i, n);
        }
    }
}

 

BFS

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

int graph[MAX][MAX];
bool visited[MAX];
int queue[MAX];
int front = 0, rear = 0;

void enqueue(int v) {
    queue[rear++] = v;
}

int dequeue() {
    return queue[front++];
}

bool isEmpty() {
    return front == rear;
}

void bfs(int start, int n) {
    enqueue(start);
    visited[start] = true;

    while (!isEmpty()) {
        int current = dequeue();
        printf("%d ", current);

        for (int i = 0; i < n; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = true;
            }
        }
    }
}

 

Java 예제

DFS

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

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

BFS

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

    queue.add(start);
    visited[start] = true;

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

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

 

Python 예제

DFS

def dfs(graph, v, visited):
    visited.add(v)
    print(v, end=' ')

    for neighbor in graph[v]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

BFS

def bfs(graph, start):
    visited = set()
    queue = [start]

    while queue:
        current = queue.pop(0)

        if current not in visited:
            print(current, end=' ')
            visited.add(current)
            queue.extend(graph[current])

---

DFS와 BFS는 그래프 탐색에서 각각의 장점과 단점을 가지며, 문제의 특성에 따라 적절히 선택해야 합니다.