BFS

다차원 배열에서 BFS, DFS 문제

그래프에서 BFS와 DFS로 순회하는 문제

정확히 짚으셨습니다! BFS는 그래프 문제에서 매우 다양하게 사용되며, 그 유형은 단순 방문 순회 외에도 거리 계산, 컴포넌트 탐색 등으로 확장됩니다.

---

✅ 대표적인 BFS 문제 유형 5가지 + 구현 예시

유형	설명	구현 여부
① 기본 순회 (연결 그래프)	정점 방문 순서 확인	✅ 예제 제공
② 1번 정점으로부터 거리 계산	단일 출발점 최단 거리	✅ 예제 제공
③ 비연결 그래프에서 전체 순회	컴포넌트 모두 탐색	✅ 예제 제공
④ 컴포넌트 개수 구하기	연결된 덩어리 수	✅ 예제 제공
⑤ 최단 거리 복원	최단 경로 자체를 출력	✅ 예제 제공 (옵션)

---

공통 준비 코드

int n = 6;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

void addEdge(int u, int v) {
    adj.get(u).add(v);
    adj.get(v).add(u);  // 무방향
}

---

✅ ① 기본 BFS 순회 (연결 그래프 기준)

void bfsTraverse(int start) {
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();

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

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

        for (int next : adj.get(curr)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.add(next);
            }
        }
    }
}

📌 출력 예: 0 1 2 3 4 5

---

✅ ② 1번 정점(0번)으로부터 모든 정점까지 거리 계산

int[] bfsDistance(int start) {
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    Queue<Integer> queue = new LinkedList<>();

    dist[start] = 0;
    queue.add(start);

    while (!queue.isEmpty()) {
        int curr = queue.poll();
        for (int next : adj.get(curr)) {
            if (dist[next] == -1) {
                dist[next] = dist[curr] + 1;
                queue.add(next);
            }
        }
    }

    return dist;
}

📌 출력 예: dist[3] = 2 → 0 → 1 → 3

---

✅ ③ 비연결 그래프에서 전체 BFS 순회

void bfsDisconnected() {
    boolean[] visited = new boolean[n];

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            visited[i] = true;

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

                for (int next : adj.get(curr)) {
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.add(next);
                    }
                }
            }
        }
    }
}

📌 출력 예: 0 1 2 (첫 컴포넌트), 3 4 (다른 컴포넌트)

---

✅ ④ 연결 컴포넌트 수 세기

int countComponents() {
    boolean[] visited = new boolean[n];
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            count++;
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            visited[i] = true;

            while (!queue.isEmpty()) {
                int curr = queue.poll();
                for (int next : adj.get(curr)) {
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.add(next);
                    }
                }
            }
        }
    }

    return count;
}

📌 출력 예: 2 (그래프가 2개 컴포넌트로 나뉨)

---

✅ ⑤ 최단 경로 복원 (거리뿐 아니라 경로도 출력)

List<Integer> bfsPath(int start, int end) {
    int[] prev = new int[n];
    Arrays.fill(prev, -1);
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[n];

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

    while (!queue.isEmpty()) {
        int curr = queue.poll();
        for (int next : adj.get(curr)) {
            if (!visited[next]) {
                visited[next] = true;
                prev[next] = curr;
                queue.add(next);
            }
        }
    }

    List<Integer> path = new ArrayList<>();
    for (int at = end; at != -1; at = prev[at]) path.add(at);
    Collections.reverse(path);
    return path;
}

📌 출력 예: 0 → 1 → 4 → [0, 1, 4]

---

✅ 총정리

유형	함수명	특징
순회	bfsTraverse(start)	방문 순서 출력
거리	bfsDistance(start)	모든 정점까지 거리
전체 순회	bfsDisconnected()	비연결 그래프 전체 방문
컴포넌트 수	countComponents()	BFS로 덩어리 수 세기
최단 경로	bfsPath(start, end)	경로 자체 복원

---

필요하면 2차원 맵 기반 BFS (미로, 토마토 문제) 또는 가중치가 0/1일 때 deque을 쓰는 BFS (0-1 BFS) 도 보여드릴 수 있어요.