[백준] 4803 트리 - 트리(Tree) + DFS(깊이우선탐색) + 분리집합(disjoint set) + 유니온파인드(Union Find) JAVA

https://www.acmicpc.net/problem/4803

4803번: 트리

코드설명

트리(Tree) + DFS(깊이우선탐색)를 활용하거나 트리(Tree) + 분리집합(disjoint set) + 유니온파인드(Union Find)를 활용하는 문제입니다.

 

처음에 유니온파인드를 통해 진행하려했지만, 

아래의 반례를 해결하지 못하여 실패했습니다.

출처 : https://www.acmicpc.net/board/view/68638
6 6
1 2
2 3
4 5
5 6
4 6
3 4
 
정답 : Case 1: No trees.
 
출력 : Case 1: There is one tree.

 

그 대신에 DFS를 활용해서 미리 방문한 곳을 다시 방문한다면 트리의 개수로 치지 않고, 새로 방문한 곳만 트리로 계산해주면서 해결해주었습니다.

코드

트리를 DFS로 활용해서 해결한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, H;
	public static int answer = 0;
	public static int[] arr;
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static boolean[] cycleCheck;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int idx = 1;
    	while(true) {
    		answer = 0;
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		M = Integer.parseInt(st.nextToken());
    		
    		if(N == 0 && M == 0) break ;
    		graph.clear();
    		cycleCheck = new boolean[N+1];
    		for(int i=0;i<N+1;i++) {
    			graph.add(new ArrayList<Integer>());
    		}
    		
    		for(int i=0;i<M;i++) {
    			st = new StringTokenizer(br.readLine());
    			int a = Integer.parseInt(st.nextToken());
    			int b = Integer.parseInt(st.nextToken());
    			graph.get(a).add(b);
    			graph.get(b).add(a);
    		}
 
    		for(int i=1;i<=N;i++) {
    			if(cycleCheck[i] == false) {
    				cycleCheck[i] = true;
    				if(dfs(-1, i) == true) answer += 1;
    			}
    		}
    		
    		if(answer == 0) {
    			System.out.println("Case "+idx+": No trees.");
    		}else if(answer == 1){
    			System.out.println("Case "+idx+": There is one tree.");
    		}else {
    			System.out.println("Case "+idx+": A forest of "+answer+" trees.");	
    		}
    		idx+=1;
    		
    	}
	}
	
	public static boolean dfs(int parent, int start) {
		for(int i=0;i<graph.get(start).size();i++) {
			int temp = graph.get(start).get(i);
			if( temp == parent) continue; //방금 지나온 부모노드일경우 PASS합니다. 이를 통해 방금 방문한곳은 가더라도 사이클로 판별하지 않습니다.
			if(cycleCheck[temp] == true) return false; //만약 이미 방문한곳이었다면, 싸이클이 발생합니다.
			cycleCheck[temp] = true; //방문처리합니다.
			if( dfs(start, temp) == false ) return false; //재귀를 통해 최종 Return 값을 결정합니다.
		}
		return true;
	}
	
}

 

 

유니온파인드로 해결하려했지만, 위의 반례를 해결하지못했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, H;
	public static int answer = 0;
	public static int[] arr;
	public static int[] parent;
	public static boolean[] cycleCheck;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int idx = 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 ;
    		
    		parent = new int[N+1];
    		cycleCheck = new boolean[N+1];
    		for(int i=1;i<N+1;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());
//    			if(findParent(a) != findParent(b)) {
//    				unionParent(a, b);
    				unionParentCheckingCycle(a,b);
//    			}
    		}
 
    		HashSet<Integer> hashset = new HashSet<Integer>();
    		for(int i=1; i<N+1;i++) {
    			if( cycleCheck[findParent(i)] == false) { //싸이클이 없을경우에만.
    				hashset.add(findParent(i));
    			}
    		}
    		
    		if(hashset.size() == 0) {
    			System.out.println("Case "+idx+": No trees.");
    		}else if(hashset.size() == 1){
    			System.out.println("Case "+idx+": There is one tree.");
    		}else {
    			System.out.println("Case "+idx+": A forest of "+hashset.size()+" trees.");	
    		}
    		idx+=1;
    		
    	}
	}
	
	public static int findParent(int x) {
		if(parent[x] == x) return x;
		return parent[x] = findParent(parent[x]);
	}
	
	public static void unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		if( a < b) parent[b] = a;
		else parent[a] = b;
	}
	
	public static void unionParentCheckingCycle(int a, int b) {
		a = findParent(a);
		b = findParent(b);
 
		if( a == b) cycleCheck[a] = true;
		
		if( a < b) parent[b] = a;
		else parent[a] = b;
	}
	
}