백준 24444·24445 Java: BFS 방문 순서와 인접 리스트 정렬

백준 24444번과 24445번은 같은 무방향 그래프를 BFS로 탐색하되, 인접 정점을 각각 오름차순과 내림차순으로 방문한다. 핵심은 각 정점의 인접 리스트를 먼저 정렬한 뒤 일반 FIFO queue로 BFS를 실행하는 것이다.

• 백준 24444번 알고리즘 수업 - 너비 우선 탐색 1
• 백준 24445번 알고리즘 수업 - 너비 우선 탐색 2

PriorityQueue가 아니라 인접 리스트를 정렬한다

“인접 정점을 오름차순으로 방문한다”는 조건은 현재 정점의 이웃을 번호 순서대로 queue에 넣으라는 뜻이다. BFS 자체의 선입선출 순서는 바꾸지 않는다.

전체 frontier를 PriorityQueue에 넣으면 이전에 먼저 발견한 정점보다 번호가 작은 정점을 뒤늦게 꺼낼 수 있다. 그러면 거리별 탐색 순서와 발견 순서가 달라져 문제에서 요구한 BFS 방문 순서가 아니다.

방문 표시도 queue에서 꺼낼 때가 아니라 넣을 때 한다. 그래야 같은 정점이 여러 이웃을 통해 중복 삽입되지 않는다.

24444: 오름차순 BFS Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int vertexCount = Integer.parseInt(tokenizer.nextToken());
        int edgeCount = Integer.parseInt(tokenizer.nextToken());
        int start = Integer.parseInt(tokenizer.nextToken());

        List<Integer>[] graph = new ArrayList[vertexCount + 1];
        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            graph[vertex] = new ArrayList<>();
        }

        for (int edge = 0; edge < edgeCount; edge++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int from = Integer.parseInt(tokenizer.nextToken());
            int to = Integer.parseInt(tokenizer.nextToken());

            graph[from].add(to);
            graph[to].add(from);
        }

        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            Collections.sort(graph[vertex]);
        }

        int[] visitOrder = new int[vertexCount + 1];
        int order = 1;

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visitOrder[start] = order++;

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

            for (int next : graph[current]) {
                if (visitOrder[next] != 0) {
                    continue;
                }

                visitOrder[next] = order++;
                queue.offer(next);
            }
        }

        StringBuilder output = new StringBuilder();
        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            output.append(visitOrder[vertex]).append('\n');
        }

        System.out.print(output);
    }
}

24445: 내림차순 BFS Java 코드

24445번은 graph 구성과 BFS는 같고, 각 인접 리스트의 정렬 방향만 바뀐다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int vertexCount = Integer.parseInt(tokenizer.nextToken());
        int edgeCount = Integer.parseInt(tokenizer.nextToken());
        int start = Integer.parseInt(tokenizer.nextToken());

        List<Integer>[] graph = new ArrayList[vertexCount + 1];
        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            graph[vertex] = new ArrayList<>();
        }

        for (int edge = 0; edge < edgeCount; edge++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int from = Integer.parseInt(tokenizer.nextToken());
            int to = Integer.parseInt(tokenizer.nextToken());

            graph[from].add(to);
            graph[to].add(from);
        }

        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            graph[vertex].sort(Comparator.reverseOrder());
        }

        int[] visitOrder = new int[vertexCount + 1];
        int order = 1;

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visitOrder[start] = order++;

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

            for (int next : graph[current]) {
                if (visitOrder[next] != 0) {
                    continue;
                }

                visitOrder[next] = order++;
                queue.offer(next);
            }
        }

        StringBuilder output = new StringBuilder();
        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            output.append(visitOrder[vertex]).append('\n');
        }

        System.out.print(output);
    }
}

같은 graph에서 순서 비교하기

두 문제의 보존된 예제 입력은 같다.

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

24444번은 인접 정점을 오름차순으로 넣으므로 정점별 방문 순서가 다음과 같다.

1
2
4
3
0

24445번은 내림차순으로 넣어 결과가 달라진다.

1
3
4
2
0

시작 정점에서 도달할 수 없는 5번 정점의 방문 순서는 0이다.

여러 번 틀렸던 이유

원문에는 ‘인접 정점을 오름차순·내림차순으로 방문’한다는 문장을 전체 후보 중 번호가 작은 정점을 먼저 뽑으라는 뜻으로 이해해 PriorityQueue를 사용했다고 적혀 있다. 여러 번 시도한 뒤 일반 queue로 바꾸고 통과했다.

문제를 다시 정리하면 정렬 대상은 queue가 아니라 graph[current]다. 이 둘을 분리하면 오름차순과 내림차순 풀이의 차이도 정렬 comparator 한 줄로 줄어든다.

그래프와 인접 리스트의 기초는 그래프, DFS와 BFS, 거리 단위로 퍼지는 BFS 응용은 백준 7569 토마토에서 이어서 볼 수 있다.

복잡도와 검증 범위

인접 리스트를 정렬하는 비용은 모든 정점에 대해 Σ O(deg(v) log deg(v))이며 O(M log N)으로 묶어 표현할 수 있다. BFS 자체는 O(N + M), 전체 공간은 O(N + M)이다.

두 Java source를 수동 검토하고 보존된 예제와 random undirected graph 80개를 독립 BFS oracle과 대조했다. 2026년 8월 2일 현재 두 BOJ URL은 채점 서비스 준비 화면이라 current judge 재제출은 확인하지 못했다.