[백준] 10451 순열 사이클 - 유니온 파인드(UnionFind, Disjoint Set) + DFS(깊이우선탐색) JAVA

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

코드설명

유니온 파인드(UnionFind, Disjoint Set) + DFS(깊이우선탐색) 를 활용합니다.

 

굳이 UnionFind를 사용하지 않고, Visited[] 배열을 생성한뒤 한번이라도 탐색했다면 Visited[] 를 true로 바꿔주면서 처리하면 더 간단하다.

 

UnionFind를 사용하고 싶어서 UnionFind를 사용했다.

코드

정답코드입니다.(처음에 틀린 함수도 함께 포함)

package Main;

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

public class Main {
    private static int N, T, K;
    private static int answer = 0;
    private static int[] standard;
    private static int[] arr;
    private static int[] parent;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			standard = new int[N + 1];
			arr = new int[N + 1];
			parent = new int[N+1];
			answer = 0;
			st = new StringTokenizer(br.readLine());
			//UnionFind 사용시 이렇게 N+1로 처리하는게 편하다.
			for(int i=1;i<=N;i++) {
				standard[i] = i;
				parent[i] = i;
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					findParent(j);
				}
				
				//아직 싸이클에 없는 경우입니다.
				if( findParent(i) == i) {
					if( simul2(i, i) == true) {
						answer += 1;
					}
				}
			}
			System.out.println(answer);
		}
		
	}
    
    private static boolean simul2(int first, int idx) {
    	if(first == arr[idx]) {
    		return true;
    	}
    	
    	simul2(first, arr[idx]);
    	unionFind(idx, arr[idx]);
    	return true;
    }
    
    //틀린 코드이다.
    //사이클은 반드시 처음 숫자값으로 돌아온다는 것을 놓쳤다.
    //또, unionFind 작업이 재귀가 끝나고 처리되는 것이 아닌 먼저 처리하고 깊이우선탐색이 지속되기에
    //올바르게 재귀가 작동하지 않는다.
    private static boolean simul(int idx) {
    	//처음에 실수한 부분. idx == arr[idx] 처리를 안했다. 본인이 본인을 바라보는 사이클을 체크해야한다.
    	if( (findParent(idx) != idx) || idx == arr[idx]) {
    		return true;
    	}
    	
    	for(int i=1; i<=N; i++) {
    		System.out.print(parent[i]+" ");
    	}
    	System.out.println();
    	System.out.println("why stackOverFlow?");
    	unionFind(idx, arr[idx]);
    	return simul(arr[idx]);
    }
    
    private static int findParent(int x) {
    	if(x == parent[x]) return x;
    	else return parent[x] = findParent(parent[x]);
    }
    
    private static void unionFind(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	
    	if(a < b) parent[b] = a;
    	else parent[a] = b;
    }
    
}