[백준/Java] 25587 : 배수로

백준 25587번 '배수로' 풀이입니다. 두 도시를 합칠 때 전체 배수 용량과 강수량의 합을 비교해야 하므로, 유니온 파인드로 대표에게 데이터를 모아 관리했습니다. 공사할 때마다 홍수 카운트를 실시간으로 갱신하는 totalFlood 변수를 활용해 매번 전체 순회 없이 O(M)에 해결했습니다.

---

📌 문제 정보

• 번호: 25587
• 제목: 배수로
• 난이도: Gold 5
• 분류: 자료 구조, 분리 집합 (Union-Find)

---

💡 접근 방식

두 도시가 연결될 때 전체 배수 용량과 강수량의 합을 비교해야 하므로, 대표에게 모든 데이터를 모아 관리하는 방식을 사용했습니다.

• 실시간 홍수 체크: totalFlood 변수를 두고, 공사를 진행할 때마다 변동 사항만 갱신하여 결과를 출력했습니다.
• 데이터 구조: cities[N][2] 2차원 배열을 활용하여 0번 인덱스에는 부모 정보를, 1번 인덱스에는 해당 집합의 도시 개수를 저장했습니다.

---

🔹 단계별 풀이

초기에는 2번 쿼리가 들어올 때마다 모든 도시를 직접 순회하며 홍수 여부를 확인하도록 구현했으나 시간 초과가 났습니다. 이를 해결하기 위해 공사할 때 미리 결과를 업데이트하도록 로직을 전환했습니다.

합치기 전 각 집합의 홍수 기여분을 빼고, 합친 후 새 상태로 다시 더하는 방식입니다.

---

💻 핵심 코드

static void construction(int city1, int city2) {
    int root1 = find(city1);
    int root2 = find(city2);

    if (root1 != root2) {
        // 합치기 전, 기존 상태 확인하여 제외
        if (rainFall[root1] > gutter[root1]) totalFlood -= cities[root1][1];
        if (rainFall[root2] > gutter[root2]) totalFlood -= cities[root2][1];

        // 합치기
        cities[root2][0] = root1;
        cities[root1][1] += cities[root2][1];
        gutter[root1] += gutter[root2];
        rainFall[root1] += rainFall[root2];

        // 합쳐진 후 재판단
        if (rainFall[root1] > gutter[root1]) totalFlood += cities[root1][1];
    }
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(M) — 경로 압축으로 합치기 연산을 상수 시간에 가깝게 처리
• 공간 복잡도: O(N)

---

📄 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] gutter;
    static int[] rainFall;
    static int[][] cities;
    static int totalFlood = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        gutter = new int[N];
        rainFall = new int[N];
        cities = new int[N][2];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            gutter[i] = Integer.parseInt(st.nextToken());
            cities[i][0] = i;
            cities[i][1] = 1;
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            rainFall[i] = Integer.parseInt(st.nextToken());
            if (rainFall[i] > gutter[i]) {
                totalFlood++;
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            if (st.nextToken().equals("1")) {
                int city1 = Integer.parseInt(st.nextToken()) - 1;
                int city2 = Integer.parseInt(st.nextToken()) - 1;
                construction(city1, city2);
            } else {
                sb.append(totalFlood).append("\n");
            }
        }
        System.out.print(sb);
    }

    static void construction(int city1, int city2) {
        int root1 = find(city1);
        int root2 = find(city2);

        if (root1 != root2) {
            if (rainFall[root1] > gutter[root1]) totalFlood -= cities[root1][1];
            if (rainFall[root2] > gutter[root2]) totalFlood -= cities[root2][1];

            cities[root2][0] = root1;
            cities[root1][1] += cities[root2][1];
            gutter[root1] += gutter[root2];
            rainFall[root1] += rainFall[root2];

            if (rainFall[root1] > gutter[root1]) totalFlood += cities[root1][1];
        }
    }

    static int find(int city) {
        if (cities[city][0] == city) return city;
        return cities[city][0] = find(cities[city][0]);
    }
}