백준 24479·24480 Java: 재귀 없이 DFS 방문 순서 맞추기

백준 24479번과 24480번은 같은 무방향 graph를 DFS로 탐색하되, 인접 정점을 각각 오름차순과 내림차순으로 방문한다. 정점이 최대 100,000개이므로 Java recursion stack에 의존하지 않고 명시적인 stack frame으로 recursive DFS의 순서를 그대로 재현할 수 있다.

• 백준 24479번 깊이 우선 탐색 1
• 백준 24480번 깊이 우선 탐색 2

단순히 이웃을 stack에 넣는 것과의 차이

recursive DFS는 현재 정점의 첫 이웃을 방문하면 그 이웃의 탐색을 끝까지 마친 뒤 다음 이웃으로 돌아온다. 각 정점과 “다음에 볼 adjacency index”를 frame에 저장하면 이 call stack 동작을 그대로 표현할 수 있다.

visited는 새 frame을 push하는 순간 표시한다. 이렇게 하면 같은 정점이 다른 경로에서 중복 push되지 않는다.

Java 코드

아래 ASCENDING을 true로 두면 24479, false로 바꾸면 24480에 제출할 수 있다.

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

public class Main {
    private static final boolean ASCENDING = true;

    private static class Frame {
        private final int vertex;
        private int nextIndex;

        private Frame(int vertex) {
            this.vertex = vertex;
        }
    }

    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());

        @SuppressWarnings("unchecked")
        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++) {
            if (ASCENDING) {
                Collections.sort(graph[vertex]);
            } else {
                graph[vertex].sort(Collections.reverseOrder());
            }
        }

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

        Deque<Frame> stack = new ArrayDeque<>();
        visited[start] = true;
        visitOrder[start] = order++;
        stack.push(new Frame(start));

        while (!stack.isEmpty()) {
            Frame current = stack.peek();
            List<Integer> neighbors = graph[current.vertex];

            if (current.nextIndex == neighbors.size()) {
                stack.pop();
                continue;
            }

            int next = neighbors.get(current.nextIndex++);
            if (visited[next]) {
                continue;
            }

            visited[next] = true;
            visitOrder[next] = order++;
            stack.push(new Frame(next));
        }

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

        System.out.print(output);
    }
}

adjacency matrix가 맞지 않는 이유

정점 100,000개의 adjacency matrix는 10^10칸이 필요해 memory limit에 맞지 않는다. adjacency list는 실제 edge만 양방향으로 두 번 저장하므로 O(V+E) 공간을 사용한다.

각 list를 정렬한 뒤 DFS가 정해진 순서로 읽는다. 정렬 비용은 모든 vertex에 대해 Σ O(deg(v) log deg(v)), 흔히 O(E log V)로 묶어 표현할 수 있다. traversal 자체는 O(V+E)다.

두 문제를 한 번에 풀었던 기록

원문에는 단계별 풀이의 1·2번 문제가 오름차순과 내림차순 차이뿐이라 Java sort 방향만 바꿔 한 번에 풀었다고 적혀 있다. 당시에는 recursive method를 사용했다.

recursion은 code가 짧지만 input에 따라 깊이가 100,000에 가까워져 StackOverflowError 위험이 있다. 명시적 frame은 heap memory를 사용하고 recursive call의 “현재 adjacency 위치”까지 보존하므로 방문 순서도 같다.

정렬 API는 compareTo와 Comparator, 같은 graph의 BFS 방문 순서는 백준 24444·24445에서 비교할 수 있다.

검증 범위

Java source를 수동 검토하고 path graph, cycle, disconnected vertex와 작은 random graph의 오름·내림차순 결과를 recursive DFS oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.