b24445. 알고리즘 수업 - 너비 우선 탐색 2

 

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

 

 

 

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

---

🔎 문제 개요

이 문제는 백준 24445번 - 알고리즘 수업 - 너비 우선 탐색 2 문제입니다.
기본적인 BFS(너비 우선 탐색) 과정은 24444번과 동일하지만,
이번에는 정점 방문 순서를 내림차순으로 정렬해야 합니다.

---

💡 예제 입력

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

💡 예제 출력

1
4
3
2
5

➡ BFS 탐색 시 정점을 큰 숫자부터 방문하도록 구현해야 합니다.

---

🛠 알고리즘 접근 방식

이 문제를 해결하는 방식은 24444번 문제와 동일하지만,
각 정점의 인접 리스트를 내림차순(Collections.reverseOrder())으로 정렬해야 합니다.

---

🔹 Java 코드 해설

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

public class b24445 {

    static int N, M, R;
    static ArrayList<Integer>[] list;
    static boolean[] isVisited;
    static Queue<Integer> q = new ArrayDeque<>();
    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 {
        for (int i = 0; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer 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++) {
            list[i].sort(Collections.reverseOrder());
        }
    }

    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 num : list[now]) {
                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);
    }
}

---

🔥 핵심 요약

✅ BFS 방식은 동일하지만, 정점 정렬 방식만 다름
✅ 24444번(오름차순 정렬) → Collections.sort() 사용
✅ 24445번(내림차순 정렬) → Collections.sort(Collections.reverseOrder()) 사용
이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊