Baekjoon 4803 트리 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."를 테스트 케이스 번호와 함께 출력한다.

풀이

해당 문제는 union-find를 이용하여 해결하였다. 다만 출력 부분을 제대로 확인하지 않았고 반례에 관해서도 한 가지가 안 떠올라 해결하는데 시간이 걸렸다.

출력 부분에서는 끝에. 이 붙는다는 것과 Case 1:를 출력해줘야 하는 것을 빼먹었다.

반례의 경우 

입력 : 

3 3
1 1
2 3
1 2
0 0

정답 :

Case 1: No trees.

해당 케이스에 대한 예외처리를 해주지 않아서 16%에서 자꾸 틀렸다는 문구가 나왔다.

로직은 아래와 같은 방식으로 구현했다.

1. 입력값을 입력받는다.

2. 입력값을 파싱 해서 둘의 부모를 비교한다.

 2-1. 부모가 다르고 둘의 부모가 0이 아니라면 union 시켜준다.

 2-2. 둘의 부모가 같다면 사이클이 생긴 경우 부모를 0으로 변경시킨다.

 2-3  둘의 부모는 다르지만 부모 중 한 명이 0인 경우 결국 연결하면 사이클이 되므로 부모 두 명 다 0으로 변경

3. 반복문을 돌면서 체크한다. i가 배열 값과 같다면 해당 배열은 최상위 루트를 의미 즉 트리 개수 1 증가

4. 출력문에 맞게 출력해준다.

코드

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

public class Main {

	static int N,M,number[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = 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;
			make();
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				if(find(a) != find(b) && find(a)!= 0 && find(b)!=0) { // 둘의 부모가 다르고, 둘다 부모가 0이아닌경우 
					union(a,b);
				}else if(find(a) == find(b)){ // 둘의 부모가 같다 즉 사이클인 경우 부모를 0으로 초기화
					number[find(a)] = 0;
				}else  { // 부모는 다른데 비교하는값중 하나의 부모가 0임 결국 사이클이 생기는 경우
					number[find(a)] = 0;
					number[find(b)] = 0;
				}
			}
			int cnt = 0;
			for (int i = 1; i < number.length; i++) { // 자기 자신을 가르킨다면 트리의 최상단임 갯수 1 증가
				if(number[i] == i)
					cnt++;
			}
			if(cnt == 0) {
				System.out.println("Case "+(t++)+": No trees.");
			}else if(cnt == 1) {
				System.out.println("Case "+(t++)+": There is one tree.");
			}else {
				System.out.println("Case "+(t++)+": A forest of "+cnt+" trees.");
			}
		}
	}
	
	static void make() {
		number = new int[N+1];
		for (int i = 1; i <=N; i++) {
			number[i] = i;
		}
	}
	
	static int find(int a) {
		if(number[a] == a)
			return a;
		return number[a] = find(number[a]);
	}
	
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a < b)
			number[b] = a;
		else 
			number[a]= b;
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드