[JAVA] 백준 4803 트리

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

풀이: 유니온파인드

1. 입력 받은 노드에 대해 유니온을 수행한다.
2. 만일 유니온시 사이클이 형성되면 root의 부모 노드를 0으로 저장한다.
3. 유니온 수행 후, 모든 노드에 대해 find를 수행하여 부모 노드가 root를 가르키도록 설정한다.
4. 0을 뺀 root노드의 개수를 카운트한다.

많이 틀릴 문제가 아닌데 틀린 부분을 찾느라 엄청 고생했다.. 내 코드의 로직과 같은 코드는 통과했는데 이유를 못 찾다가 while문 안에 조건문을 잘못 넣어서 발생한 문제였다.
!(node==0&&m=0) -> node != 0 || m != 0
or 이 아닌 and 연산자를 넣어서 0이 하나라도 있는 입력이 있을 시 코드가 종료되어서 틀린 답이 나왔다.

코드

package baekjoon.gold.g4;

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

public class p4803트리 {
	static int[] parent;

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

	static boolean union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		if (rootA == rootB) {
			parent[rootB] = rootA;
			parent[rootA] = 0;
			return false;
		} else if (rootA < rootB) {
			parent[rootB] = rootA;
		} else {
			parent[rootA] = rootB;
		}
		return true;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int node = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int testcase = 1;
		while (node != 0 || m != 0) {
			parent = new int[node + 1];
			for (int i = 0; i < node + 1; i++)
				parent[i] = i;
			HashSet<Integer> tree = new HashSet<>();
			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);
			}
			for (int i = 1; i <= node; i++) {
				int pi = find(i);
				if (pi > 0)
					tree.add(pi);
			}
			if (tree.isEmpty())
				System.out.println("Case " + testcase + ": No trees.");
			else if (tree.size() == 1)
				System.out.println("Case " + testcase + ": There is one tree.");
			else
				System.out.println("Case " + testcase + ": A forest of " + tree.size() + " trees.");
			testcase++;
			st = new StringTokenizer(br.readLine());
			node = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
		}

	}
}