[백준] 20040 사이클 게임 - 트리(Tree) + 분리집합(disjoint set) + 유니온파인드(Union Find) JAVA

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

20040번: 사이클 게임

코드설명

트리(Tree) + 분리집합(disjoint set) + 유니온파인드(Union Find) 문제입니다.

 

처음에는 DFS를 활용하여 진행하려했습니다.

만약에 노드의 정점이 첫 시작이 반드시 0 으로 시작했다면, DFS를 통해서도 진행할 수 있었겠지만, 그렇지 않기에 DFS로 진행하지 못합니다. 만약, DFS를 사용하려면, hashset으로 현재까지 나온 Index값을 가지고서 해당 값들을 DFS를 통해 해결할 수 있겠지만 비효율적을 보이기에 유니온파인드를 통해 만약 새로 들어온 값이 findParent를 하였을때 같은 값으로 맞추어진다면 싸이클이 발생한것으로 해당 작업의 순서를 출력시키고 중단시키면됩니다.

 

처음에 사용해보려던 DFS코드입니다.

//	언제 싸이클이 발생되었는지 시점을 알기 위해 DFS를 사용하지 못한다. DFS를 사용하려면, hashset으로 현재까지 나온 Index값을 가지고서 해당 값들을 DFS를 통해 해결할 수 있겠지만 비효율적으로 보인다.
public static boolean dfs(int parent, int child) {
    for(int i=0;i<graph.get(child).size();i++) {
        int now = graph.get(child).get(i);
        if(parent == now) continue;
        if(visited[now] == true) return false;
        visited[now] = true;
        if(dfs(child, now) == false) return false;
    }
    return true;
}

 

코드

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 boolean[] visited;
	public static int[] parent;
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
 
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	visited = new boolean[N];
    	parent = new int[N];
    	for(int i=0;i<N;i++) {
    		parent[i] = i;
    	}
    	for(int i=0;i<N;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());
    		
    		if(findParent(a) == findParent(b)) {
    			System.out.println( (i+1) );
    			return ;
    		}
    		else if(findParent(a) != findParent(b)) { 
    			unionParent(a, b);
    		}
    	}
    	
    	System.out.println(0);
    	
	}
	
	public static int findParent(int x) {
		if( x == parent[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) visited[a] = true; //싸이클이 발생한 시점이다.
		
		if( a < b) parent[b] = a;
		else parent[a] = b;
	}
	
	
}