b24444. 알고리즘 수업 - 너비 우선 탐색 1

 

https://www.acmicpc.net/problem/24444

 

 

 

📌 자바(Java)로 푸는 너비 우선 탐색(BFS) - 백준 24444 문제 풀이 🚀

---

🔎 문제 개요

이 문제는 백준 24444번 - 알고리즘 수업 - 너비 우선 탐색 1 문제입니다.
주어진 그래프를 너비 우선 탐색(BFS) 하면서 방문 순서를 기록해야 합니다.
각 정점은 오름차순으로 방문해야 하며, 방문 순서는 result[] 배열에 저장해야 합니다.

---

💡 예제 입력

5 5 1
1 4
1 2
2 3
2 4
3 4

💡 예제 출력

1
2
3
4
5

➡ 1번 정점부터 BFS 탐색하며 방문 순서를 출력해야 합니다.

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 BFS(너비 우선 탐색) + 정렬을 활용합니다.

✏️ 주요 고려 사항

✔ BFS를 사용하여 그래프를 탐색
✔ 간선 정보를 저장할 때 오름차순으로 정렬
✔ 정점 방문 순서를 result[] 배열에 기록
✔ 큐(Queue)를 사용하여 BFS를 구현

---

🔹 Java 코드 해설

import java.util.*;
import java.io.*;

public class Main {

    static int N, M, R; // 정점 수, 간선 수, 시작 정점
    static ArrayList<Integer>[] list; // 인접 리스트
    static boolean[] isVisited; // 방문 여부 저장 배열
    static Queue<Integer> q = new ArrayDeque<>(); // BFS를 위한 큐
    static int[] result; // 방문 순서 저장 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = stoInt(st.nextToken()); // 정점 개수
        M = stoInt(st.nextToken()); // 간선 개수
        R = stoInt(st.nextToken()); // 시작 정점

        isVisited = new boolean[N + 1]; // 방문 여부 배열
        result = new int[N + 1]; // 방문 순서 배열
        list = new ArrayList[N + 1];

        inputAndSort(br); // 입력 및 정렬

        BFS(R); // BFS 실행

        printResult(); // 결과 출력
    }

    // 입력 및 정렬 처리
    private static void inputAndSort(BufferedReader br) throws IOException {
        StringTokenizer st;
        for (int i = 0; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int a = stoInt(st.nextToken());
            int b = stoInt(st.nextToken());

            list[a].add(b);
            list[b].add(a);
        }

        // 각 리스트를 오름차순 정렬
        for (int i = 0; i <= N; i++) {
            Collections.sort(list[i]);
        }
    }

    // 문자열을 정수로 변환하는 함수
    static int stoInt(String s) {
        return Integer.parseInt(s);
    }

    // BFS 구현
    static void BFS(int r) {
        int count = 1; // 방문 순서 카운트
        q.add(r);
        isVisited[r] = true;

        while (!q.isEmpty()) {
            int now = q.poll();
            result[now] = count++;

            for (int i = 0; i < list[now].size(); i++) {
                int num = list[now].get(i);
                if (!isVisited[num]) {
                    q.add(num);
                    isVisited[num] = true;
                }
            }
        }
    }

    // 결과 출력
    private static void printResult() {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(result[i]).append("\n");
        }
        System.out.println(sb);
    }
}

---

🔍 코드 설명

📌 1. 입력 처리 및 그래프 초기화

N = stoInt(st.nextToken()); // 정점 개수
M = stoInt(st.nextToken()); // 간선 개수
R = stoInt(st.nextToken()); // 시작 정점

isVisited = new boolean[N + 1]; // 방문 여부 배열
result = new int[N + 1]; // 방문 순서 배열
list = new ArrayList[N + 1];

• 정점 개수(N), 간선 개수(M), 시작 정점(R) 을 입력받음
• isVisited[] 배열을 사용하여 방문 여부를 기록
• result[] 배열을 사용하여 방문 순서를 저장
• list[] 배열을 사용하여 인접 리스트를 저장

---

📌 2. 간선 정보 입력 및 오름차순 정렬

for (int i = 0; i <= N; i++) {
    list[i] = new ArrayList<>();
}

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());

    int a = stoInt(st.nextToken());
    int b = stoInt(st.nextToken());

    list[a].add(b);
    list[b].add(a);
}

// 각 리스트를 오름차순 정렬
for (int i = 0; i <= N; i++) {
    Collections.sort(list[i]);
}

• ArrayList[]를 사용하여 인접 리스트 방식으로 간선 정보를 저장
• 정점 번호가 작은 순서대로 방문하기 위해 Collections.sort()로 정렬

---

📌 3. BFS 탐색

BFS(R);

• 시작 정점(R)부터 BFS 탐색을 시작

---

📌 4. BFS 탐색 구현

static void BFS(int r) {
    int count = 1; // 방문 순서 카운트
    q.add(r);
    isVisited[r] = true;

    while (!q.isEmpty()) {
        int now = q.poll();
        result[now] = count++;

        for (int i = 0; i < list[now].size(); i++) {
            int num = list[now].get(i);
            if (!isVisited[num]) {
                q.add(num);
                isVisited[num] = true;
            }
        }
    }
}

• BFS를 실행하면서 방문 순서를 기록
• 큐(Queue)를 사용하여 탐색
• 방문하지 않은 정점들을 차례대로 방문

---

📌 5. 결과 출력

private static void printResult() {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= N; i++) {
        sb.append(result[i]).append("\n");
    }
    System.out.println(sb);
}

• 각 정점의 방문 순서를 출력

---

🔥 시간 복잡도 분석

연산	최악의 경우 수행 횟수	시간 복잡도
간선 입력 및 정렬	M log M	O(M log M)
BFS 탐색	N + M	O(N + M)
총합		O(N + M log M)

✅ 빠른 BFS 탐색이 가능하며, 그래프의 크기가 크더라도 효율적

---

🏆 정리

✅ 핵심 포인트

✔ BFS를 사용하여 그래프를 탐색하며 방문 순서를 기록
✔ 정점이 작은 숫자부터 방문해야 하므로 오름차순 정렬
✔ 방문 순서는 result[] 배열을 사용하여 저장

---

🎯 이 알고리즘의 장점

✅ BFS를 활용하여 빠르게 탐색 가능
✅ 인접 리스트 + 정렬을 통해 정점 방문 순서 제어 가능
✅ O(N + M log M) 시간 복잡도로 효율적인 탐색 가능

---

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다!