그래프 탐색 알고리즘 DFS(Depth First Search)와 BFS(Breadth First Search)

그래프 탐색은 컴퓨터 과학에서 중요한 문제이며, 많은 알고리즘이 이 문제를 해결하기 위해 고안되었습니다. 이 글에서는 그래프 탐색 알고리즘 중 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS)을 설명하고 각각의 특징과 구현 방법을 알아보겠습니다. 우리는 Java와 C 언어로 구현 예제를 제공하여, 두 언어를 사용하는 독자들이 직접 실행해볼 수 있도록 돕겠습니다.

그래프 탐색이란?

그래프 탐색은 그래프의 모든 노드를 방문하거나 특정 노드를 찾기 위해 수행되는 알고리즘입니다. 그래프는 노드와 노드 간의 연결(간선)으로 이루어진 자료 구조로, 많은 실제 문제를 해결하는 데 사용됩니다. 그래프 탐색은 크게 두 가지 방식으로 나뉩니다: DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색).

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

DFS는 한 방향으로 가능한 깊이까지 탐색한 후, 더 이상 갈 곳이 없으면 이전 노드로 돌아가서 다른 방향으로 다시 깊이 탐색하는 방식입니다. 이는 스택 자료 구조를 사용하여 구현할 수 있으며, 재귀를 사용해 간결하게 구현할 수도 있습니다.

DFS 특징

• 스택을 사용해 구현하거나 재귀 호출을 통해 구현할 수 있습니다.
• 그래프의 깊숙한 부분까지 먼저 탐색합니다.
• 경로를 추적하기 위해서 방문 여부를 기록해야 합니다.

Java로 구현한 DFS 예제

import java.util.*;

public class GraphDFS {
    private LinkedList<Integer>[] adjList;
    private boolean[] visited;

    public GraphDFS(int vertices) {
        adjList = new LinkedList[vertices];
        visited = new boolean[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int src, int dest) {
        adjList[src].add(dest);
    }

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

        for (int neighbor : adjList[start]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }

    public static void main(String[] args) {
        GraphDFS graph = new GraphDFS(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);

        System.out.println("DFS 탐색 결과:");
        graph.dfs(0);
    }
}

C 언어로 구현한 DFS 예제

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

#define MAX 100

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

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

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

int main() {
    vertices = 6;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            graph[i][j] = 0;
        }
        visited[i] = false;
    }

    graph[0][1] = 1;
    graph[0][2] = 1;
    graph[1][3] = 1;
    graph[1][4] = 1;
    graph[2][5] = 1;

    printf("DFS 탐색 결과:\n");
    dfs(0);

    return 0;
}

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

BFS는 그래프 탐색에서 시작 노드로부터 가까운 노드부터 차례대로 방문하는 방식입니다. 이는 큐 자료 구조를 사용하여 구현됩니다. 각 단계에서 방문할 수 있는 모든 이웃 노드를 큐에 넣고, 큐에서 하나씩 꺼내면서 탐색을 진행합니다.

BFS 특징

• 큐 자료 구조를 사용해 구현합니다.
• 그래프의 넓은 부분부터 탐색합니다.
• 경로를 추적하기 위해서 방문 여부를 기록해야 합니다.

Java로 구현한 BFS 예제

import java.util.*;

public class GraphBFS {
    private LinkedList<Integer>[] adjList;
    private boolean[] visited;

    public GraphBFS(int vertices) {
        adjList = new LinkedList[vertices];
        visited = new boolean[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int src, int dest) {
        adjList[src].add(dest);
    }

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

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

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

    public static void main(String[] args) {
        GraphBFS graph = new GraphBFS(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);

        System.out.println("BFS 탐색 결과:");
        graph.bfs(0);
    }
}

C 언어로 구현한 BFS 예제

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

#define MAX 100

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

void bfs(int start) {
    int queue[MAX];
    int front = 0, rear = 0;

    visited[start] = true;
    queue[rear++] = start;

    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

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

int main() {
    vertices = 6;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            graph[i][j] = 0;
        }
        visited[i] = false;
    }

    graph[0][1] = 1;
    graph[0][2] = 1;
    graph[1][3] = 1;
    graph[1][4] = 1;
    graph[2][5] = 1;

    printf("BFS 탐색 결과:\n");
    bfs(0);

    return 0;
}

DFS와 BFS의 차이점

특성	DFS	BFS
자료 구조	스택 (재귀 또는 명시적 스택)	큐
탐색 순서	한 경로로 끝까지 탐색	가까운 노드부터 탐색
메모리 사용	방문할 노드만 스택에 저장	모든 인접 노드를 큐에 저장
사용 예시	미로 문제, 백트래킹	최단 경로 문제

DFS는 그래프의 특정 경로를 탐색하거나, 경로의 깊이를 우선 탐색해야 할 때 적합합니다. 반면, BFS는 노드 간의 최단 거리를 찾거나, 특정 레벨의 모든 노드를 탐색해야 할 때 유용합니다.

마무리

이 글에서는 그래프 탐색의 두 가지 기본적인 알고리즘인 DFS와 BFS에 대해 설명하고, Java와 C 언어로 구현 예제를 제공했습니다. DFS는 깊이 있는 탐색을, BFS는 너비 있는 탐색을 수행합니다. 각 알고리즘은 문제의 성격에 따라 적합한 방법을 선택하여 사용해야 합니다. 다양한 그래프 문제를 직접 구현하고 테스트하면서 이 알고리즘들을 더욱 깊이 이해할 수 있을 것입니다.