[Java] 백준 BOJ / 4803번: 트리

트리

문제

---

문제 설명

그래프의 정점과 간선의 정보가 주어졌을 때 트리의 개수를 세는 문제이다.

이 문제에서 유의해야할 점은 싸이클 발생 여부이므로 유니온 파인드로 풀기로 하였다.

주어진 간선들의 정보로 노드들을 연결시키고 Union 과정을 통해서 사이클을 판별하고 루트 노드에 대한 정보를 입력하고 사이클을 제외한 루트 노드를 세어주면 트리의 개수를 셀 수 있다.

---

구현

문제에서 주요하게 사용하는 알고리즘은 유니온 파인드 이다.

일단 Find 함수를 사용하여 두 노드의 부모 노드를 탐색한 후 부모 노드가 다르다면 한 쪽의 노드로 합치는 작업을 수행한다.

static int find(int x) {
	if (x == parent[x])
    	return x;
	else
    	return parent[x] = find(parent[x]);
    }

Union 과정에서는 정점에 대해서 Find 함수를 실행하여 부모 노드를 찾는다. 두 부모 노드가 같다면 이미 방문한 노드를 다시 방문 했다는 뜻이므로 사이클이 발생했다는 뜻이다.

따라서 두 노드가 같을 경우 유니온 작업을 진행한 후에 다른 한쪽을 0으로 초기화하여 방문했다는 표시를 한다.

static void union(int u, int v) {
	u = find(u);
	v = find(v);

	if (u == v) {
		parent[v] = u;
		parent[u] = 0;
	}
    else if (u < v)
    	parent[v] = u;
	else
    	parent[u] = v;
}

이후 HashSet을 이용하여 중복되는 부모 노드를 체크하며 0이 아닌 노드를 추가하고, 이 HashSet의 크기가 트리의 개수가 된다.

Set<Integer> tree = new HashSet<>();
for (int i = 1; i <= n; i++) {
	if (find(parent[i]) > 0)
		tree.add(find(parent[i]));
}

이렇게 완성된 HashSet을 기반으로 출력조건에 맞게 출력해주면 된다.

---

코드

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

public class Main_4803 {
    static int[] parent;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int cnt = 1;

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            if (n == 0 && m == 0) break;

            sb.append("Case ").append(cnt++).append(": ");
            parent = new int[n + 1];
            for (int i = 1; i <= n; i++) parent[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);
            }

            Set<Integer> tree = new HashSet<>();
            for (int i = 1; i <= n; i++) {
                if (find(parent[i]) > 0)
                    tree.add(find(parent[i]));
            }

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

        System.out.println(sb);
    }

    static void union(int u, int v) {
        u = find(u);
        v = find(v);

        if (u == v) {
            parent[v] = u;
            parent[u] = 0;
        }
        else if (u < v) parent[v] = u;
        else parent[u] = v;
    }

    static int find(int x) {
        if (x == parent[x]) return x;
        else return parent[x] = find(parent[x]);
    }
}