백준 1781번 컵라면 — Union-Find로 푸는 방법 정리

📍 문제 요약

각 문제는 (deadline, ramen) 형태로 주어진다.
즉, 해당 deadline일까지 풀면 ramen 개수를 얻을 수 있는 문제다.

하루에 문제를 1개만 풀 수 있을 때,
얻을 수 있는 컵라면의 최대 개수를 구하는 문제다.

---

🪄 아이디어

1. 정렬 기준

   • 컵라면 수(count)가 많은 순서로 (내림차순)
   • 마감일(deadline)이 빠른 순서로 (오름차순)

2. 핵심 논리

   • 컵라면이 많은 문제부터 가능한 가장 늦은 날짜(≤ deadline)에 배치한다.
   • 이미 차 있는 날이면, 왼쪽으로 한 칸씩 이동하며 빈 날을 찾는다.
   • 더 이상 갈 데가 없으면(0이 되면), 해당 문제는 버린다.

---

💡 예시

입력:
4
3 2
3 4
3 4
2 5

정렬 결과 👇

deadline	count
2	5
3	4
3	4
3	2

가장 많은 컵라면(5)은 deadline=2 안에 풀어야 하므로
1~2일 중 가장 늦은 날(2일차)에 배치된다.

---

⚙️ 1차 풀이 — 단순 DFS (시간 초과)

빈칸을 찾을 때마다 왼쪽으로 한 칸씩 이동 → O(N) 탐색 발생

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int[] parent;

    public static void main(String[] args) throws IOException {

        int N = Integer.parseInt(br.readLine());
        parent = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            parent[i] = i;
        }


        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.count == o2.count) {
                return Integer.compare(o1.deadline, o2.deadline);
            }
            return Integer.compare(o2.count, o1.count);
        });

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int deadline = Integer.parseInt(st.nextToken());
            int count = Integer.parseInt(st.nextToken());
            pq.add(new Node(deadline, count));
        }

        long cnt = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if(parent[node.deadline] == node.deadline) {
                cnt += node.count;
                parent[node.deadline] = node.deadline - 1;
            }else{
                int pos = dfs(node.deadline);
                if(pos == 0) continue;
                parent[pos] = pos - 1;
                cnt += node.count;
            }
        }

        System.out.println(cnt);
    }

    static private int dfs(int cur) {
        if(parent[cur] == cur){
            return cur;
        }

        return dfs(parent[cur]);
    }

    static class Node {
        int deadline, count;

        public Node(int deadline, int count) {
            this.deadline = deadline;
            this.count = count;
        }
    }
}

⚠️ 문제점: 매번 왼쪽으로 한 칸씩 이동하면서 빈칸을 찾기 때문에 시간 초과 발생

⚡ 2차 풀이 — Union-Find (좌표 압축)

빈칸 탐색을 O(1)로 줄이기 위해
parent[cur] = dfs(parent[cur])로 경로 압축(Path Compression)을 적용한다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int[] parent;

    public static void main(String[] args) throws IOException {

        int N = Integer.parseInt(br.readLine());
        parent = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            parent[i] = i;
        }


        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.count == o2.count) {
                return Integer.compare(o1.deadline, o2.deadline);
            }
            return Integer.compare(o2.count, o1.count);
        });

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int deadline = Integer.parseInt(st.nextToken());
            int count = Integer.parseInt(st.nextToken());
            pq.add(new Node(deadline, count));
        }

        long cnt = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if(parent[node.deadline] == node.deadline) {
                cnt += node.count;
                parent[node.deadline] = node.deadline - 1;
            }else{
                int pos = dfs(node.deadline);
                if(pos == 0) continue;
                parent[pos] = pos - 1;
                cnt += node.count;
            }
        }

        System.out.println(cnt);
    }

    static private int dfs(int cur) {
        if(parent[cur] == cur){
            return cur;
        }

        return parent[cur] = dfs(parent[cur]);
    }

    static class Node {
        int deadline, count;

        public Node(int deadline, int count) {
            this.deadline = deadline;
            this.count = count;
        }
    }
}

🔍 핵심 비교 요약

구분	1차 풀이	2차 풀이
탐색 방법	매번 왼쪽으로 순차 이동	🧩 Union-Find 경로 압축
시간 복잡도	🕒 O(N²)	⚡ O(N log N)
차이점	return dfs(parent[cur]);	return parent[cur] = dfs(parent[cur]);
결과	❌ 시간 초과	✅ 통과

💬 한 줄 정리

Union-Find의 경로 압축(Path Compression)을 적용하면
"빈칸 탐색"을 O(N)에서 O(1) 수준으로 최적화할 수 있다.