Java로 DFS, BFS 알고리즘 정리

개요

그래프 탐색은 코딩 테스트와 실무 모두에서 핵심적인 알고리즘입니다. 이 글에서는 DFS(깊이 우선 탐색) 와 BFS(너비 우선 탐색) 의 개념을 정리하고, Java로 직접 구현해 봅니다.

---

그래프 표현

모든 예제에서 사용할 인접 리스트 기반 그래프입니다.

import java.util.*;

public class Graph {
    private int vertices;
    private List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        this.adjList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src); // 무방향 그래프
    }

    public List<Integer> getNeighbors(int vertex) {
        return adjList.get(vertex);
    }

    public int getVertices() {
        return vertices;
    }
}

---

1. DFS (깊이 우선 탐색)

개념

DFS는 한 경로를 끝까지 탐색한 뒤, 더 이상 갈 곳이 없으면 이전 분기점으로 되돌아가(backtrack) 다른 경로를 탐색하는 방식입니다.

• 스택(Stack) 또는 재귀(Recursion)를 사용합니다.
• 트리의 전위 순회(pre-order traversal)와 동일한 원리입니다.

재귀 구현

public class DFSRecursive {

    public static void dfs(Graph graph, int start) {
        boolean[] visited = new boolean[graph.getVertices()];
        dfsHelper(graph, start, visited);
    }

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

        for (int neighbor : graph.getNeighbors(vertex)) {
            if (!visited[neighbor]) {
                dfsHelper(graph, neighbor, visited);
            }
        }
    }

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

        System.out.print("DFS (재귀): ");
        dfs(graph, 0);
        // 출력: 0 1 3 4 2 5
    }
}

스택 구현

재귀 대신 명시적 스택을 사용하면 스택 오버플로를 방지할 수 있습니다.

public class DFSIterative {

    public static void dfs(Graph graph, int start) {
        boolean[] visited = new boolean[graph.getVertices()];
        Deque<Integer> stack = new ArrayDeque<>();

        stack.push(start);

        System.out.print("DFS (스택): ");
        while (!stack.isEmpty()) {
            int vertex = stack.pop();

            if (visited[vertex]) {
                continue;
            }

            visited[vertex] = true;
            System.out.print(vertex + " ");

            // 인접 노드를 역순으로 push하면 재귀 버전과 같은 순서가 됩니다
            List<Integer> neighbors = graph.getNeighbors(vertex);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                }
            }
        }
    }

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

        dfs(graph, 0);
        // 출력: 0 1 3 4 2 5
    }
}

---

2. BFS (너비 우선 탐색)

개념

BFS는 시작 노드에서 가까운 노드부터 레벨(level) 순서로 탐색하는 방식입니다.

• 큐(Queue)를 사용합니다.
• 최단 경로 문제(가중치 없는 그래프)에 적합합니다.

큐 구현

public class BFS {

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

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

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

            for (int neighbor : graph.getNeighbors(vertex)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }

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

        bfs(graph, 0);
        // 출력: 0 1 2 3 4 5
    }
}

BFS로 최단 거리 구하기

public class BFSShortestPath {

    public static int[] shortestPath(Graph graph, int start) {
        int[] distance = new int[graph.getVertices()];
        Arrays.fill(distance, -1);

        Queue<Integer> queue = new LinkedList<>();
        distance[start] = 0;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();

            for (int neighbor : graph.getNeighbors(vertex)) {
                if (distance[neighbor] == -1) {
                    distance[neighbor] = distance[vertex] + 1;
                    queue.offer(neighbor);
                }
            }
        }

        return distance;
    }

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

        int[] dist = shortestPath(graph, 0);
        for (int i = 0; i < dist.length; i++) {
            System.out.println("0 -> " + i + " : " + dist[i]);
        }
        // 0 -> 0 : 0
        // 0 -> 1 : 1
        // 0 -> 2 : 1
        // 0 -> 3 : 2
        // 0 -> 4 : 2
        // 0 -> 5 : 2
    }
}

---

3. 시간/공간 복잡도 비교

항목	DFS	BFS
시간 복잡도	O(V + E)	O(V + E)
공간 복잡도	O(V) — 재귀 스택 또는 명시적 스택	O(V) — 큐
최악 공간	O(V) — 경로 깊이만큼	O(V) — 가장 넓은 레벨만큼

V = 정점(Vertex) 수, E = 간선(Edge) 수

시간 복잡도는 동일하지만, 공간 사용 패턴이 다릅니다.

• DFS: 깊고 좁은 그래프에서 메모리 효율적
• BFS: 얕고 넓은 그래프에서 메모리 효율적

---

4. 언제 DFS vs BFS를 사용하는가?

DFS를 선택하는 경우

• 모든 경로 탐색: 가능한 모든 경우의 수를 탐색해야 할 때 (백트래킹)
• 사이클 탐지: 그래프에 사이클이 존재하는지 확인할 때
• 위상 정렬: DAG에서 작업 순서를 결정할 때
• 연결 요소 탐색: 그래프의 연결된 컴포넌트를 찾을 때
• 미로 탈출: 한 방향으로 끝까지 가 보는 전략이 자연스러울 때

BFS를 선택하는 경우

• 최단 경로: 가중치가 없는 그래프에서 최단 거리를 구할 때
• 레벨별 탐색: 트리의 레벨 순서 순회가 필요할 때
• 최소 횟수 문제: "최소 몇 번 만에 도달할 수 있는가" 유형 문제
• 네트워크 전파: 바이러스 확산, 소셜 네트워크 친구 추천 등

요약 표

상황	추천 알고리즘
최단 경로 (비가중 그래프)	BFS
모든 경로 탐색 / 백트래킹	DFS
사이클 탐지	DFS
위상 정렬	DFS
레벨별 순회	BFS
연결 요소	DFS 또는 BFS

---

마무리

DFS와 BFS는 그래프 탐색의 가장 기본이 되는 알고리즘입니다. 두 알고리즘의 동작 원리를 확실히 이해하고, 문제 유형에 따라 적절한 탐색 방법을 선택하는 것이 중요합니다. 코딩 테스트에서 자주 등장하므로 위 코드를 직접 타이핑하며 손에 익혀 두시길 권장합니다.