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

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

1. BFS (Breadth-First Search)

추가 정리 필요

• 중요한 포인트 : 큐에 넣을 때 방문 표시하기 (뺄 때하면 시간 초과 가능성)
• 응용 문제들
  • 거리를 찾아야 한다면 true/false 대신 숫자로 거리 저장 (+1씩)
  • 띄엄띄엄 덩어리 : for문으로 시작점 찾아서 bfs 진행
  • 시작점이 여러개라면? : 처음에 시작점들을 모두 큐에 넣어두고 bfs 진행
  • 1차원 bfs : 백준의 숨바꼭질 문제, 범위 잘 확인하기, 상하좌우 대신이라고 생각
  • 백준 불 4179 문제 : 단방향 영향, 불 먼저 시간 bfs 진행 후 사람 탈출 시간 bfs 진행 (조건 확인)
  • 백준 18809 문제 : 양방향 영향, 동시에 bfs 진행해야 함 = 백트레킹을 알아야 함

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

• 시간 복잡도: O(V + E)
  • 정점 수: V, 간선 수: E

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

• 시간 복잡도
  • 격자 크기: N × M
  • 시간 복잡도: O(N × M)
    • 각 좌표를 최대 한 번씩 방문
    • 각 방향(4개) 체크 → 상수 시간
• 예제
  • 상하좌우 네 방향으로 이동 가능한 BFS 탐색입니다.
  • 0은 이동 가능, 1은 벽(이동 불가)로 가정합니다.
  • start부터 도착지까지 최단 경로를 찾는 구조로 설계되어 있습니다.
• 코드 설명
  • 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});
                    }
                }
            }
        }
    }
}

2. DFS (Depth-First Search)

추가 정리 필요

• bfs에서 스택으로 바뀌면 dfs다
• dfs는 거리 계산 불가능
  • 굳이 다차원 배열에서 dfs 쓸 일 없음
  • dfs는 그래프, 트리에서 사용할 수 있음

재귀로 구현

• 시간 복잡도: O(V + E)
  • 정점 수: V, 간선 수: E

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);
                    }
                }
            }
        }
    }
}

---

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