BFS 심화 — 최단 거리부터 다차원 탐색까지

미로에서 최단 경로를 찾으려면 어떻게 해야 할까요? 한 걸음씩 사방으로 퍼져나가면 됩니다. 이것이 BFS입니다.

BFS 기본 복습

너비 우선 탐색(Breadth-First Search)은 시작 노드에서 가까운 노드부터 레벨 단위로 탐색하는 알고리즘입니다.

JAVA

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

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

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

        for (int next : graph.get(node)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

왜 BFS가 최단 경로를 보장하는가

BFS는 시작점으로부터의 ** 거리가 d인 노드를 모두 방문한 뒤** d+1인 노드를 방문합니다. 따라서 가중치가 없는(또는 모두 동일한) 그래프에서 ** 처음 도달한 시점이 최단 거리 **입니다.

JAVA

// 최단 거리 구하기
public static int[] shortestPath(List<List<Integer>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);

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

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

        for (int next : graph.get(node)) {
            if (dist[next] == -1) {
                dist[next] = dist[node] + 1;
                queue.offer(next);
            }
        }
    }
    return dist;
}

레벨별 탐색

큐에서 한 레벨을 통째로 처리하고 다음 레벨로 넘어가는 패턴입니다. 트리의 레벨 순회, 최단 거리 단계별 카운트에 유용합니다.

JAVA

public static int bfsLevel(List<List<Integer>> graph, int start, int target) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.offer(start);
    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size(); // 현재 레벨의 노드 수

        for (int i = 0; i < size; i++) {
            int node = queue.poll();
            if (node == target) return level;

            for (int next : graph.get(node)) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        level++;
    }
    return -1;
}

2차원 격자 BFS

미로, 지도 탐색 등에서 가장 많이 사용되는 패턴입니다.

JAVA

public static int shortestPathGrid(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    int[] dy = {0, 0, -1, 1};

    boolean[][] visited = new boolean[rows][cols];
    Queue<int[]> queue = new LinkedList<>();

    visited[0][0] = true;
    queue.offer(new int[]{0, 0, 0}); // {row, col, distance}

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int r = curr[0], c = curr[1], dist = curr[2];

        if (r == rows - 1 && c == cols - 1) return dist;

        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && !visited[nr][nc] && grid[nr][nc] == 0) {
                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc, dist + 1});
            }
        }
    }
    return -1;
}

멀티소스 BFS

** 여러 시작점에서 동시에 BFS**를 수행하는 기법입니다. "가장 가까운 X까지의 거리"를 모든 칸에 대해 구할 때 유용합니다.

JAVA

// 격자에서 모든 칸의 가장 가까운 1까지의 거리
public static int[][] multiSourceBFS(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dist = new int[rows][cols];
    Queue<int[]> queue = new LinkedList<>();

    // 모든 소스(1인 칸)를 초기 큐에 넣음
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                dist[i][j] = 0;
                queue.offer(new int[]{i, j});
            } else {
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();

        for (int d = 0; d < 4; d++) {
            int nr = curr[0] + dx[d], nc = curr[1] + dy[d];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && dist[nr][nc] > dist[curr[0]][curr[1]] + 1) {
                dist[nr][nc] = dist[curr[0]][curr[1]] + 1;
                queue.offer(new int[]{nr, nc});
            }
        }
    }
    return dist;
}

각 소스에서 따로 BFS를 하면 O(K × V)이지만, 멀티소스 BFS는 O(V + E)에 해결합니다.

0-1 BFS

간선 가중치가 0 또는 1인 그래프에서 최단 경로를 구하는 기법입니다. Dijkstra(O(E log V)) 대신 Deque 를 사용하여 O(V + E) 에 해결합니다.

JAVA

public static int[] zeroOneBFS(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerFirst(start);

    while (!deque.isEmpty()) {
        int node = deque.pollFirst();

        for (int[] edge : graph.get(node)) {
            int next = edge[0], weight = edge[1]; // weight는 0 또는 1

            if (dist[node] + weight < dist[next]) {
                dist[next] = dist[node] + weight;

                if (weight == 0) {
                    deque.offerFirst(next); // 가중치 0: 앞에 삽입
                } else {
                    deque.offerLast(next);  // 가중치 1: 뒤에 삽입
                }
            }
        }
    }
    return dist;
}

가중치 0인 간선을 앞에 넣으면, 항상 거리가 작은 노드부터 처리됩니다.

양방향 BFS (Bidirectional BFS)

시작점과 끝점 양쪽에서 동시에 BFS를 수행하여, 두 탐색이 만나면 종료합니다. 탐색 공간을 O(b^d)에서 O(b^(d/2))로 줄일 수 있습니다.

JAVA

public static int bidirectionalBFS(Map<Integer, List<Integer>> graph,
                                    int start, int end) {
    if (start == end) return 0;

    Set<Integer> frontSet = new HashSet<>(Set.of(start));
    Set<Integer> backSet = new HashSet<>(Set.of(end));
    Set<Integer> visited = new HashSet<>();
    int level = 0;

    while (!frontSet.isEmpty() && !backSet.isEmpty()) {
        // 항상 작은 쪽에서 확장 (최적화)
        if (frontSet.size() > backSet.size()) {
            Set<Integer> temp = frontSet;
            frontSet = backSet;
            backSet = temp;
        }

        Set<Integer> nextSet = new HashSet<>();
        for (int node : frontSet) {
            for (int next : graph.getOrDefault(node, List.of())) {
                if (backSet.contains(next)) return level + 1;
                if (!visited.contains(next)) {
                    visited.add(next);
                    nextSet.add(next);
                }
            }
        }
        frontSet = nextSet;
        level++;
    }
    return -1;
}

백엔드/실무에서의 연결

웹 크롤러

웹 크롤러는 BFS 기반으로 동작합니다. 시작 URL에서 링크를 따라가며, 같은 깊이(홉 수)의 페이지를 먼저 방문합니다.

JAVA

// 웹 크롤러의 BFS 구조 (개념)
Queue<String> urlQueue = new LinkedList<>();
Set<String> visited = new HashSet<>();

urlQueue.offer("https://example.com");
visited.add("https://example.com");

while (!urlQueue.isEmpty()) {
    String url = urlQueue.poll();
    List<String> links = fetchAndExtractLinks(url);

    for (String link : links) {
        if (!visited.contains(link)) {
            visited.add(link);
            urlQueue.offer(link);
        }
    }
}

소셜 네트워크의 친구 추천

"2촌 관계" = BFS에서 레벨 2. 친구의 친구를 추천하는 기능은 BFS 레벨 탐색입니다.

네트워크 브로드캐스트

네트워크에서 패킷이 퍼져나가는 방식은 멀티소스 BFS와 유사합니다. 각 라우터에서 이웃 라우터로 전파됩니다.

Garbage Collection

Java GC의 Mark 단계에서 루트 객체에서 시작하여 도달 가능한 객체를 탐색하는 과정에 BFS가 사용될 수 있습니다.

주의할 점

방문 체크를 큐에 넣을 때가 아니라 꺼낼 때 하는 실수

BFS에서 방문 체크를 큐에서 꺼낼 때 하면, 같은 노드가 큐에 여러 번 들어가 메모리가 폭발하거나 시간 초과가 발생합니다. 반드시 큐에 넣는 시점에 방문 표시를 해야 합니다.

가중치가 있는 그래프에서 BFS를 적용하는 실수

BFS는 가중치가 없는(또는 모든 간선 가중치가 동일한) 그래프에서만 최단 경로를 보장합니다. 가중치가 0과 1뿐이면 0-1 BFS(Deque), 다양하면 Dijkstra를 사용해야 합니다.

정리

BFS 변형	용도	자료구조	시간 복잡도
기본 BFS	최단 경로 (가중치 동일)	Queue	O(V + E)
레벨별 BFS	단계별 처리	Queue + size	O(V + E)
멀티소스 BFS	여러 시작점에서 최단 거리	Queue	O(V + E)
0-1 BFS	가중치 0/1 최단 경로	Deque	O(V + E)
양방향 BFS	양끝에서 만남 탐색	2개 Set	O(b^(d/2))

기억할 포인트:

BFS는 가중치 없는 그래프에서 최단 경로를 보장 합니다.
레벨별 탐색은 queue.size()로 현재 레벨의 노드 수를 고정하는 것이 핵심입니다.
멀티소스 BFS는 여러 시작점을 동시에 처리하여 효율을 높입니다.
0-1 BFS는 Deque를 사용하여 Dijkstra보다 빠르게 동작합니다.