자바 코딩테스트 강좌, DFS와 BFS 프로그램

알고리즘 문제 해결 능력을 기르는 것은 소프트웨어 개발자에게 매우 중요합니다. 특히 취업 준비를 하고 있는 경우, 다양한 알고리즘과 자료구조를 이해하고 활용하는 능력이 필요합니다. 본 강좌에서는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 개념을 이해하고, 실제 알고리즘 문제를 풀어보겠습니다. 이 과정에서는 문제 정의, 접근 방식, 자바 코드 구현 및 시간 복잡도를 함께 살펴보겠습니다.

문제 정의

주어진 문제는 다음과 같습니다:

문제: 0에서 N까지의 정점으로 구성된 무방향 그래프가 주어질 때, 특정한 시작 정점에서 시작하여 모든 정점에 도달할 수 있는지를 확인하는 프로그램을 작성하라. 두 가지 방법인 DFS와 BFS를 사용하여 이 문제를 해결해보자.

문제 접근 방식

그래프 탐색 알고리즘은 깊이 우선 탐색과 너비 우선 탐색의 두 가지 주요 방법이 있습니다. 이 두 가지 방식은 각각의 특징과 활용도가 다릅니다. 따라서, 문제를 풀기 위해 두 가지 방법의 구현을 준비하겠습니다.

1. DFS (Depth First Search)

DFS는 깊이를 우선으로 탐색하여 그래프의 최대 깊이까지 내려간 후, 더 이상 방문할 수 있는 정점이 없을 때 돌아오는 방식입니다. 이 방식은 스택을 활용하여 구현하거나 재귀 함수를 통해 쉽게 구현할 수 있습니다.

DFS 구현

다음은 DFS를 사용하여 그래프를 탐색하는 자바 코드입니다:

import java.util.*;

public class Graph {
    private int vertices;
    private LinkedList[] adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source); // 무방향 그래프
    }

    public void dfs(int start) {
        boolean[] visited = new boolean[vertices];
        dfsUtil(start, visited);
    }

    private void dfsUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (Integer neighbor : adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }
}

2. BFS (Breadth First Search)

BFS는 너비를 우선으로 탐색하여 현재 정점의 이웃을 먼저 탐색한 후, 그 이웃의 이웃을 탐색하는 방식입니다. 주로 큐를 사용하여 구현합니다.

BFS 구현

다음은 BFS를 사용하여 그래프를 탐색하는 자바 코드입니다:

import java.util.*;

public class Graph {
    private int vertices;
    private LinkedList<Integer>[] adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source); // 무방향 그래프
    }

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

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

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

            for (Integer neighbor : adjacencyList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

코드 실행 예제

이제 DFS와 BFS를 이용하여 그래프를 탐색하는 예제를 실행해보겠습니다. 아래 코드는 그래프를 생성하고 두 가지 방식으로 탐색을 수행합니다:

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

        System.out.println("DFS Traversal:");
        graph.dfs(0);

        System.out.println("\nBFS Traversal:");
        graph.bfs(0);
    }
}

시간 복잡도 분석

DFS와 BFS의 시간 복잡도는 다음과 같습니다:

DFS: O(V + E) 여기서 V는 정점(Vertex)의 수, E는 간선(Edge)의 수입니다.
BFS: O(V + E) 그래프의 모든 정점과 간선을 한 번씩 방문합니다.

결론

DFS와 BFS는 그래프 탐색을 위한 기초적인 알고리즘입니다. 이 두 가지 알고리즘을 이해하고 활용함으로써, 다양한 문제를 해결할 수 있습니다. 본 강좌를 통해 그래프의 기본 개념과 구현 방법을 익혔다면, 더 복잡한 문제에 도전할 준비가 되었다고 할 수 있습니다. 이후에는 실제 코딩 테스트에서 자주 등장하는 다양한 문제를 풀어보며 이론을 실습으로 연결해보는 것이 좋습니다.

추후에는 더 다양한 자료구조와 알고리즘을 학습하여 여러분의 프로그래밍 실력을 한 단계 끌어올리길 바랍니다.