(코테) [Java] BFS

BFS란?

Breadth-First Search, 너비 우선 탐색은 루트 노드에서 시작해서 가까운 노드부터 탐색하는 방식임

• 큐(Queue) 자료구조를 사용해 구현함
• DFS가 깊이부터 들어가는 반면, BFS는 넓게 퍼지듯이 탐색

BFS 동작 원리

1. 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤, 인접한 노드들을 모두 큐에 넣고 방문 처리
3. 큐가 빌 때까지 반복

BFS 기본 구조 (Java)

void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int current = queue.poll();
        for (int next : graph[current]) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

예제: 인접 리스트 BFS

import java.util.*;

public class Main {
    static List<Integer>[] graph;
    static boolean[] visited;

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);

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

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 정점 수
        int m = sc.nextInt(); // 간선 수

        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u); // 무방향 그래프
        }

        bfs(1); // 1번 정점부터 BFS 시작
    }
}

---

BFS 탐색 예시

입력:

5 4
1 2
1 3
2 4
3 5

탐색 순서 (시작: 1):

1 2 3 4 5

BFS 특징 요약

항목 설명

구현 방식	큐(Queue) 사용
방문 순서	시작 노드 → 가까운 노드부터
시간 복잡도	O(N + M) (N: 노드 수, M: 간선 수)
용도	최단 거리 구하기, 레벨별 탐색

코테 풀 때 봤었던

1. dx, dy 활용해서 주변까지 탐색 후 이동 (4방향, 8방향)
2. 큐에다가 좌표만 담는게 아니라 거리 및 시간 같은 추가 값을 달아서 계속 이동하는 방식
   1. [x,y,dist] 이런식으로 거리를 추가로 입력!

문제풀 때 알고리즘 포함해서 항상 어떻게 풀지를 아는게 중요한거 같음!

그래서 계속해서 더 많이 풀어보고 노력하는 중임 ㅠ

정리

• BFS는 가장 먼저 도착하는 방법을 찾는 데 유리함
• Java에서는 Queue와 visited 배열을 통해 구현함
• 최단 거리, 레벨 순서, 퍼지는 구조 문제에서 자주 등장함