[알고리즘] 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS)

너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)에 대해 공부 후 정리하였습니다.

Summary - BFS

• 그래프나 트리에서 가까운 정점부터 너비를 우선으로 탐색하는 알고리즘
• 큐(Queue)를 사용하여 구현
• 문제에 따라 다르지만 그래프의 경우 O(V + E), 2차원 배열의 경우 O(NM)
• 최단 거리 탐색, 미로 문제, 네트워크 탐색 등에 많이 사용

1. BFS (Breadth-First Search)

1️⃣ 개념

BFS는 시작 정점에서 가까운 정점부터 너비를 우선으로 차례대로 탐색하는 알고리즘이다.
(=다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘)

2️⃣ 특징

• 레벨 단위 탐색 → 가까운 정점(최단 거리)을 먼저 방문
• 큐(Queue) 자료구조 사용 (큐에 쌓이는 순서는 반드시 거리 순임)
• 시작점부터 연결된 다른 모든 점까지의 최단 경로 찾을 수 있어서 최단 거리 문제에서 자주 활용됨 (가중치가 없는 경우)
• 방문 여부 체크가 반드시 필요

3️⃣ 시간 복잡도

그래프 BFS (인접리스트) = 모든 정점과 간선을 확인해야 하므로 O(V + E) (정점 수: V, 간선 수: E)
2차원 배열 BFS = 격자 크기(N × M), 각 좌표를 최대 한 번씩 방문하므로 O(N × M) (방향 체크는 상수 시간)

4️⃣ 구현 방법

1. 시작 칸을 큐에 넣고 방문 처리
2. 큐에서 원소를 꺼내며 인접 정점 확인
3. 방문했었다면 continue, 방문하지 않은 칸이라면 방문했다는 표시를 남기고 큐에 추가
4. 큐가 빌 때까지 2번 과정을 반복

구현 시 주의할 부분

• 시작점에 방문 표시했는지 확인하기
• 큐에서 넣을 때 방문했다믄 표시하기 (큐에서 뺄 때 방문 표시X)
• 이웃한 원소의 범위 확인하기

5️⃣ 예시 코드

그래프의 BFS (인접리스트)

import java.util.*;

public class BFSExample {
    static int n = 6; // 정점의 수
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited = new boolean[n + 1]; // 정점 번호가 1부터 시작한다고 가정

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 예시 간선 추가 (무방향 그래프)
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(3, 6);

        // BFS 시작 (1번 정점에서 시작)
        bfs(1);
    }

    // 간선 추가 함수
    static void addEdge(int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u); // 무방향 그래프일 경우만 필요
    }

    // BFS 구현
    static void bfs(int start) {
        Deque<Integer> queue = new ArrayDeque<>();
        visited[start] = true;
        queue.offer(start); // 시작 노드 큐에 추가

        while (!queue.isEmpty()) {
            int current = queue.poll(); // 큐에서 하나 꺼냄
            System.out.print(current + " ");

            // 현재 노드의 인접 노드 탐색
            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    visited[next] = true; // 방문 처리
                    queue.offer(next); // 다음 노드를 큐에 추가
                }
            }
        }
    }
}

2차원 배열의 BFS

• 예제
  • 상하좌우 네 방향으로 이동 가능
  • 0은 이동 가능, 1은 이동 불가
• 코드 설명
  • int[][] map : 2차원 배열
  • int[][] dist : 시작 지점으로부터 각 지점까지의 거리
  • boolean[][] visited : 방문 여부
  • int[] dx, dy : 방향 벡터 (상하좌우)

import java.util.*;

public class BFS2D {
    static int N = 5;
    static int M = 6;

    // 미로 (0: 이동 가능, 1: 벽)
    static int[][] map = {
        {0, 1, 0, 0, 0, 0},
        {0, 1, 0, 1, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {1, 1, 0, 0, 0, 1},
        {0, 0, 0, 1, 0, 0}
    };

    static int[][] dist = new int[N][M]; // 거리 저장
    static boolean[][] visited = new boolean[N][M];

    // 상, 하, 좌, 우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        bfs(0, 0); // (0, 0)부터 시작

        System.out.println("도착지까지 거리: " + dist[N - 1][M - 1]); // 도착 좌표까지 거리 출력
    }

    static void bfs(int x, int y) {
        Deque<int[]> queue = new ArrayDeque<>();
        visited[x][y] = true;
        dist[x][y] = 1; // 시작 지점 거리 1로 설정
        queue.offer(new int[]{x, y});

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

            for (int d = 0; d < 4; d++) {
                int nx = cx + dx[d];
                int ny = cy + dy[d];

                // 범위 체크 + 벽이 아님 + 미방문일 때
                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (!visited[nx][ny] && map[nx][ny] == 0) {
                        visited[nx][ny] = true;
                        dist[nx][ny] = dist[cx][cy] + 1;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

6️⃣ 자주 사용하는 곳

• 최단 거리 탐색 (가중치가 없는 그래프)
• 미로 탐색 문제
• 네트워크 연결 여부 확인
• Flood Fill (영역 채우기 문제)
• SNS/웹 크롤링 (친구 관계, 링크 탐색)

문제 구현 예시

• BOJ 1926번 : 띄엄띄엄 덩어리 찾으려면 이중 for문으로 시작점 찾아서 BFS 진행하기 - O(NM)
• BOJ 2178번 : 다차원 배열에서의 거리 측정은 -1로 채워진 다차원 int배열에 거리 저장하기 (+1씩, -1이 아니라면 방문한 칸임을 확인할 수 있음)
• BOJ 7576번 : 시작점이 여러 개일 때, 모든 시작점들을 큐에 넣어두고 BFS 진행하기
• BOJ 4179번 : 시작점이 두 종류일 때, 불 BFS를 진행해서 각 칸에 전파되는 시간 구한 후 사람 탈출 BFS를 진행하는데 시간 조건 확인하기 (단방향 영향, 불만 사람에게 영향 줌)
• BOJ 18809번 : 시작점이 두 종류인데 양방향 영향일 때, 백트래킹 이용해서 시간 순으로 동시 진행 필요 (양방향 영향, 불과 물이 만나면 상호작용)
• BOJ 1697번 : 1차원에서의 BFS는 조건인 이동 방법이 상하좌우 대신이라고 생각하기 + 움직이는 범위 잘 확인하기

---

Summary - DFS

• 그래프나 트리에서 가까운 정점부터 깊이를 우선으로 탐색하는 알고리즘
• 재귀나 스택을 이용하여 구현
• 그래프를 인접리스트로 구현한 경우 O(V + E), 인접행렬의 경우 O(V^2)
• 그래프 탐색, 경로 찾기, 사이클 탐지, 백트래킹 등에 많이 사용

2. DFS (Depth-First Search)

1️⃣ 개념

DFS는 시작 노드에서 한 경로를 따라 끝까지 탐색한 후, 더 이상 진행할 수 없으면 이전 분기점으로 돌아가 다른 경로를 탐색하는 알고리즘이다.
(=다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘)

2️⃣ 특징

• 재귀 함수 또는 스택(Stack)으로 구현 가능 (BFS에서 스택으로 바뀌면 DFS와 동일)
• 모든 노드를 빠짐없이 방문 가능
• 경로의 깊이를 우선적으로 탐색하기 때문에 백트래킹과 잘 어울림
• 거리를 구할 수 없어서 다차원 배열에서 사용을 잘 안함 (그래프, 트리에서 사용할 수 있음)

3️⃣ 시간 복잡도

• 그래프를 인접리스트로 구현 시 O(V + E) (정점 수: V, 간선 수: E)
• 그래프를 인접 행렬로 구현하면 O(V^2)

4️⃣ 구현 방법

1. 시작 노드를 스택에 넣고 방문 처리
2. 스택에서 원소를 꺼내 연결된 노드 중 방문하지 않았다면, 방문 처리 후 스택에 삽입
3. 스택이 빌 때까지 2번 과정 반복

5️⃣ 예시 코드

재귀로 구현

import java.util.*;

public class DFSExample {
    static int n = 6; // 정점의 수
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited = new boolean[n + 1]; // 정점 번호가 1부터 시작한다고 가정

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 예시 간선 추가 (무방향 그래프)
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(3, 6);

        // DFS 시작 (1번 정점에서 시작)
        dfs(1);
    }

    // 간선 추가 함수
    static void addEdge(int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u); // 무방향 그래프일 경우
    }

    // DFS 재귀 함수
    static void dfs(int current) {
        visited[current] = true; // 현재 노드 방문 처리
        System.out.print(current + " ");

        // 현재 노드의 인접 노드 순회
        for (int next : graph.get(current)) {
            if (!visited[next]) {
                dfs(next); // 아직 방문하지 않은 노드라면 재귀 호출
            }
        }
    }
}

스택으로 구현

import java.util.*;

public class DFSStackExample {
    static int n = 6; // 정점의 수
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited = new boolean[n + 1];

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 예시 간선 추가 (무방향 그래프)
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(3, 6);

        // DFS 시작 (1번 정점에서 시작)
        dfsStack(1);
    }

    // 간선 추가 함수
    static void addEdge(int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u); // 무방향 그래프
    }

    // 스택을 이용한 DFS 함수
    static void dfsStack(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int current = stack.pop();

            if (!visited[current]) {
                visited[current] = true;
                System.out.print(current + " ");

                // 인접 노드를 스택에 추가 (작은 번호 먼저 방문하려면 정렬 필요)
                // 기본적으로는 큰 번호부터 넣어야 작은 번호가 먼저 나옴
                List<Integer> neighbors = graph.get(current);
                Collections.sort(neighbors, Collections.reverseOrder());

                for (int next : neighbors) {
                    if (!visited[next]) {
                        stack.push(next);
                    }
                }
            }
        }
    }
}

6️⃣ 자주 사용하는 곳

• 그래프 탐색 (연결 요소 개수 구하기)
• 경로 찾기 (특정 노드까지 도달 가능한지 확인)
• 사이클 탐지
• 백트래킹 기반 문제 (순열, 조합, 부분 집합, 미로 탐색 등)

---

3. 전체 요약 정리

항목	DFS	BFS
구현 방식	재귀 / 스택	큐
방문 순서	깊이 우선	너비 우선
자료 구조	Stack (재귀 호출 시 call stack 사용)	Queue
시간 복잡도	O(V + E)	O(V + E), O(NM)
용도 예시	미로 경로 찾기, 백트래킹	최단 경로 탐색