📌 자바(Java)로 푸는 트리 - 백준 4803 🌳

사이클 탐지 + 연결 요소(트리) 개수 구하기 (Union-Find)

🔎 문제 개요

백준 4803 - 트리 문제는,

주어진 그래프에서 사이클이 없는 연결 요소(트리)를 찾아야 하는 문제입니다.
하나의 그래프 안에 여러 개의 트리가 있을 수 있으며,
사이클이 있는 연결 요소는 트리로 취급하지 않습니다.

💡 예제 입력

💡 예제 출력

Case 1: A forest of 2 trees.
Case 2: No trees.

🛠 알고리즘 접근 방식

이 문제는 전형적인 Union-Find(Disjoint Set) 알고리즘에

✔ 사이클 감지를 덧붙이는 문제입니다.

📌 핵심 자료구조

p[i] : i번 노드의 부모를 나타냅니다.
사이클이 발생한 집합은 루트를 0으로 만들어서 트리가 아님을 표시합니다.

📌 초기화

p = new int[N+1];
for (int i = 0; i <= N; i++)
    p[i] = i;

✔ 각 노드의 부모를 자기 자신으로 초기화합니다.

📌 간선 연결 (Union 연산)

int pa = find(a);
int pb = find(b);
if (pa > pb) {
    int temp = pa;
    pa = pb;
    pb = temp;
}
if (pa == pb) {
    p[pa] = 0; // 사이클 발생
}
else {
    p[pb] = p[pa]; // 루트 병합
}

✔ 두 노드의 루트를 찾아 합칩니다.

✔ 이미 같은 집합이라면, 사이클이 발생한 것으로 보고 루트를 0으로 설정합니다.

📌 부모 찾기 (Find 연산)

static int find(int a){
    if(p[a] == a) return a;
    return p[a] = find(p[a]);
}

✔ 경로 압축(Path Compression)을 적용하여 find 속도를 최적화합니다.

📌 최종 트리 개수 세기

HashSet<Integer> set = new HashSet<>();
for (int i = 1; i <= N; i++) {
    int tree = find(i);
    if (tree > 0)
        set.add(tree);
}

✔ 루트가 0이 아닌 노드들을 집합에 추가해

✔ 트리의 개수를 센다.

📌 출력 포맷

if (set.size() == 1)
    sb.append("There is one tree.\n");
else if (set.isEmpty())
    sb.append("No trees.\n");
else
    sb.append("A forest of " + set.size() + " trees.\n");

✔ 트리 개수에 따라 맞는 문구를 출력합니다.

✅ 정리

핵심 포인트	설명
사이클이 생기면 루트를 0으로 세팅	사이클 발생 시 해당 연결 요소를 트리로 취급하지 않기
find()에서 경로 압축	시간 복잡도 최적화 (거의 O(1))
set으로 고유한 루트만 카운트	트리의 개수를 정확히 구하기 위함

🔥 코드 전체 (정리)

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

public class b4803 {
    static int N, M;
    static int[] p;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int cnt = 1;
        
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            if (N == 0 && M == 0) break;

            p = new int[N+1];
            for (int i = 0; i <= N; i++)
                p[i] = i;

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                union(a, b);
            }

            sb.append("Case ").append(cnt++).append(": ");
            HashSet<Integer> set = new HashSet<>();
            for (int i = 1; i <= N; i++) {
                int tree = find(i);
                if (tree > 0)
                    set.add(tree);
            }

            if (set.size() == 1)
                sb.append("There is one tree.\n");
            else if (set.isEmpty())
                sb.append("No trees.\n");
            else
                sb.append("A forest of ").append(set.size()).append(" trees.\n");
        }
        System.out.println(sb);
    }

    static int find(int a) {
        if (p[a] == a) return a;
        return p[a] = find(p[a]);
    }

    static void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa > pb) {
            int temp = pa;
            pa = pb;
            pb = temp;
        }
        if (pa == pb) {
            p[pa] = 0;
        } else {
            p[pb] = p[pa];
        }
    }
}