[BOJ] 24480 - 알고리즘 수업 깊이 우선 탐색 2(Java)

문제 설명

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

---

접근법

기본적인 DFS 문제처럼 보이지만, 한 가지 제약 조건 때문에 흥미로운 최적화를 시도해볼 수 있었습니다.

이 문제는 주어진 무방향 그래프를 깊이 우선 탐색(DFS)으로 순회하는 문제입니다. 시작 정점 R에서부터 탐색을 시작하며, 각 정점의 방문 순서를 출력해야 합니다.

핵심적인 제약 조건은 다음과 같습니다.

인접 정점은 내림차순으로 방문해야 한다.

예를 들어, 현재 정점 5에 연결된 인접 정점이 [1, 4, 2] 라면, 우리는 [4, 2, 1] 순서로 방문해야 합니다. 이 조건 때문에 일반적인 DFS 구현 방식에 약간의 수정이 필요했습니다.

List와 Collections.sort() 를 통한 첫번째 접근

가장 직관적으로 떠올릴 수 있는 방법은 ArrayList로 그래프를 구현하고, DFS 탐색 시 인접 정점 리스트를 매번 내림차순으로 정렬하는 것입니다.

// 그래프 선언
List<List<Integer>> graph = new ArrayList<>();

// DFS 함수 내부
public void dfs(int curr) {
    visited[curr] = true;
    result[curr] = count++;

    // 매번 재귀 호출 시 정렬 수행
    Collections.sort(graph.get(curr), Collections.reverseOrder());

    for (int next : graph.get(curr)) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

이 방법은 한 가지 비효율이 숨어있습니다. DFS는 재귀적으로 동작하기 때문에, dfs() 함수가 호출될 때마다 Collections.sort()가 반복적으로 실행될 수 있습니다. 정점의 차수(degree)가 클수록 이 정렬 과정의 부담은 무시할 수 없게 됩니다. 물론, 이 문제에서는 각 정점을 한 번만 방문하므로 정렬도 한 번만 일어납니다. 하지만 '정렬이 필요한 탐색'이라는 문제 유형에서 더 효율적인 구조는 없을까 고민하게 되었습니다.

PriorityQueue로 정렬 자동화

"내림차순으로 방문한다"는 것은 "방문할 노드 중 가장 번호가 큰 노드부터 방문한다"는 의미와 같습니다. 여기서 '가장 큰 값부터 처리한다'는 힌트를 얻어 우선순위 큐를 떠올렸습니다. Java에서 우선순위큐는 기본적으로 최소 힙(Min Heap)으로 구현되지만, 생성 시 Comparator를 전달하여 최대 힙(Max Heap)으로 동작하게 할 수 있습니다.

// 그래프를 PriorityQueue의 리스트로 선언
List<PriorityQueue<Integer>> graph = new ArrayList<>();

// 각 정점의 인접 리스트를 최대 힙으로 초기화
for (int i = 0; i <= N; i++) {
    graph.add(new PriorityQueue<>(Collections.reverseOrder()));
}

이렇게 그래프를 구성하면 어떤 장점이 있을까요?

1. 자동 정렬: 요소를 추가할 때마다 O(log n)의 시간 복잡도로 자동 정렬됩니다.
2. 효율적인 추출: poll() 메서드를 호출하면 항상 가장 큰 값이 O(log n)의 시간 복잡도로 추출됩니다.

이제 DFS 코드는 훨씬 간결하고 효율적으로 변합니다.

// 개선된 DFS
public static void dfs(int curr) {
    visited[curr] = true;
    result[curr] = count++;

    // 매번 정렬할 필요 없이, 가장 큰 값을 poll() 하기만 하면 된다.
    PriorityQueue<Integer> pq = graph.get(curr);
    while (!pq.isEmpty()) {
        int next = pq.poll(); // 알아서 가장 큰 값이 나옴
        if (!visited[next]) {
            dfs(next);
        }
    }
}

Collections.sort()를 호출하던 부분이 사라지고, while (!pq.isEmpty()) 루프 안에서 pq.poll()을 호출하는 것만으로 '내림차순 방문' 조건이 완벽하게 해결되었습니다. PriorityQueue가 데이터의 삽입/삭제 과정에서 이미 정렬 상태를 유지해주기 때문입니다.

---

코드

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

public class Main {
    static List<PriorityQueue<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static int N, M, R, count=1;
    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 = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        visited = new boolean[N+1];
        result = new int[N+1];

        for(int i=0; i<=N; i++){
            graph.add(new PriorityQueue<>(Collections.reverseOrder()));
        }

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

            int firstPoint = Integer.parseInt(st.nextToken());
            int secondPoint = Integer.parseInt(st.nextToken());
            graph.get(firstPoint).add(secondPoint); //무방향 그래프
            graph.get(secondPoint).add(firstPoint);
        }

        dfs(R);

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=N; i++){
            sb.append(result[i]).append("\\n");
        }

        System.out.println(sb);
    }

    public static void dfs(int curr){
        visited[curr] = true;
        result[curr] = count++;

        PriorityQueue<Integer> pq = graph.get(curr);
        while (!pq.isEmpty()) {
            int next = pq.poll();
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
}

---

마무리

단순히 List와 sort()를 이용해도 해결할 수 있는 문제였지만, PriorityQueue라는 자료구조의 특성을 활용하여 더 효율적인 코드를 작성할 수 있었습니다. 문제의 요구사항 속에서 '반복되는 정렬'이나 '최대/최소값 찾기' 같은 패턴이 보인다면 PriorityQueue를 떠올려보는 습관을 들이면 좋을 것 같습니다.