[BOJ] 백준 4803번 트리 (Java)

#4803 트리

난이도 : 골드 4

유형 : 자료구조 / Union-Find

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

 

문제 풀이  

주어진 노드와 간선들을 연결하여 트리의 갯수를 세어주는 문제이다. 유의해야할 점은 싸이클 발생 여부이다. 그러니 당연히 유니온 파인드로 풀이를 하였다. 물론 DFS로 해도 상관없다.

 

설계 및 구현

주어진 간선들의 정보로 노드들을 연결시켜 union과정에서 싸이클 판별 및 루트 노드에 대한 정보를 입력해주면 된다. 모든 간선들의 입력이 끝난 후 루트 노드를 세어주면 되는데 여기서 싸이클 판별했던 트리들은 제거해주면 된다.

 

고민해야 할 부분은 싸이클을 어떻게 판별하냐이다. 무차별적으로 싸이클이 발생하면 해당 노드들의 정보를 모두 저장해도 되고 아니면 루트노드에만 특정 표시를 해줘도 된다. 나는 초반에 전자로 풀었다가 다듬는 과정에서 후자로 리팩토링하였다.

 

싸이클이 발생하는 트리 - 모든 노드 저장하여 판별하기

처음에는 이렇게 무작정 싸이클이 발생하는 모든 노드들을 Set에 저장한 다음 모든 루트 노드를 조회할 때 제외시켜줬다. 

+ treeSet 데이터 구하는 과정에서 루트 노드를 find(i)로 구해야하는데 parents[i]로 구해서 헤맸었다. 오랜만에 써보니 감이 떨어졌나보다

Set<Integer> cycleList = 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());

	int ra = find(a);
	int rb = find(b);
	if(ra==rb) { // cycle
		cycleList.add(ra);
		cycleList.add(rb);
	}else {
		if(cycleList.contains(ra) || cycleList.contains(rb)){ // cycle
			cycleList.add(ra);
			cycleList.add(rb);
		}
		union(a,b);
	}
}

Set<Integer> treeSet = new HashSet<>();
for(int i=1; i<n+1; i++) {
	if(!cycleList.contains(find(i))) {
		treeSet.add(find(i));	
	}
}

static void union(int x, int y) {
	int rx= find(x);
	int ry= find(y);
	if(ry < rx) {
		int tmp = rx;
		rx = ry;
		ry = tmp;
	}
	parents[ry] = rx;
}

 

싸이클이 발생하는 트리 - 루트 노드로만 판별하기

좀 더 깔끔하게 하고자 union메서드에서 싸이클을 판별하였다. 그리고 노드의 인덱스가 1~n이기 때문에 싸이클이 되는 루트 노드는 0으로 표기함으로써 후에 해당 트리에 대한 싸이클의 여부를 판별해줬다. 사실 별 차이없는데 union-find 오랜만에 써보는지라 다시 감을 익히고자 리팩토링해봤다.

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> treeSet = new HashSet<>();
for(int i=1; i<n+1; i++) {
	int ra = find(i);
	if(ra >0) {
		treeSet.add(ra);	
	}
}

static void union(int x, int y) {
	int rx= find(x);
	int ry= find(y);
	if(ry < rx) {
		int tmp = rx;
		rx = ry;
		ry = tmp;
	}
	// cycle
	if(rx==ry) {
		parents[rx] = 0;
	}
	else {
		parents[ry] = rx;
	}
}

 

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	static int[] parents;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int idx=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;
			
			parents = new int[n+1];
			for(int i=1; i<n+1; i++) {
				parents[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> treeSet = new HashSet<>();
			for(int i=1; i<n+1; i++) {
				int ra = find(i);
				if(ra >0) {
					treeSet.add(ra);	
				}
			}
            
			int treeNum= treeSet.size();
			if(treeNum ==0) {
				sb.append("Case " + idx +": ").append("No trees.\n");
			}else if(treeNum ==1) {
				sb.append("Case " + idx +": ").append("There is one tree.\n");
			}else if(treeNum >1){
				sb.append("Case " + idx +": ").append("A forest of "+ treeNum+" trees.\n");
			}
			idx++;
		}
		
		System.out.println(sb.toString());
	}
	
	static int find(int x) {
		if(parents[x] ==x) return x;
		return find(parents[x]);
	}
	
	static void union(int x, int y) {
		int rx= find(x);
		int ry= find(y);
		if(ry < rx) {
			int tmp = rx;
			rx = ry;
			ry = tmp;
		}
		// cycle
		if(rx==ry) {
			parents[rx] = 0;
		}
		else {
			parents[ry] = rx;
		}
	}
}