자료구조 · 알고리즘 기초집LESSON 20

BFS와 DFS: 맵 탐색과 연결 요소 찾기

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

20강. BFS와 DFS: 맵 탐색과 연결 요소 찾기

1. 이번 강의에서 해결할 문제

스테이지 그래프에서 시작점과 가까운 순서로 탐색하거나 한 경로를 끝까지 조사하려면 방문 중복과 순환을 안전하게 처리해야 합니다.

2. 학습 목표

3. 핵심 개념

BFS는 큐를 사용해 시작점에서 간선 수가 가까운 정점부터 방문하므로 가중치 없는 최단 간선 수를 구할 수 있습니다. DFS는 한 경로를 깊게 탐색해 연결 요소, 백트래킹의 기반이 됩니다. 둘 다 정점을 큐나 스택에 넣는 시점에 방문 표시하면 중복 예약을 막을 수 있습니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/GraphSearch.java

src/GraphSearch.java
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class GraphSearch {
    static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
        java.util.ArrayList<Integer> order = new java.util.ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(start); visited.add(start);
        while (!queue.isEmpty()) {
            int current = queue.poll(); order.add(current);
            for (int next : graph.getOrDefault(current, List.of())) {
                if (visited.add(next)) queue.offer(next);
            }
        }
        return order;
    }

    static List<Integer> dfs(Map<Integer, List<Integer>> graph, int start) {
        java.util.ArrayList<Integer> order = new java.util.ArrayList<>();
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (!visited.add(current)) continue;
            order.add(current);
            List<Integer> neighbors = graph.getOrDefault(current, List.of());
            for (int i = neighbors.size() - 1; i >= 0; i--) stack.push(neighbors.get(i));
        }
        return order;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, List.of(2, 3)); graph.put(2, List.of(1, 4));
        graph.put(3, List.of(1, 4)); graph.put(4, List.of(2, 3));
        System.out.println("BFS: " + bfs(graph, 1));
        System.out.println("DFS: " + dfs(graph, 1));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/GraphSearch.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/GraphSearch.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\GraphSearch.java
java -cp .\out GraphSearch

예상 결과: 이웃 목록 순서를 기준으로 BFS는 [1, 2, 3, 4], DFS는 [1, 2, 4, 3]을 출력합니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

BFS는 큐에 넣을 때 방문 표시해 같은 정점이 여러 번 예약되는 것을 막습니다. DFS는 명시적 스택에서 꺼낼 때 이미 처리한 정점을 건너뛰고, 이웃을 역순으로 push해 주어진 인접 목록의 앞 원소부터 방문합니다. 두 방식 모두 각 정점과 인접 간선을 제한된 횟수만 확인해 O(V+E) 시간, 큐·스택과 방문 집합에 O(V) 공간을 사용합니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ