find,union

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?contestProbId=AWngfZVa9XwDFAQU&solveclubId=AYWesuzK3nUDFAQK&problemBoxTitle=5%EC%A3%BC%EC%B0%A8&problemBoxCnt=4&probBoxId=AYchVEmqEvYDFASR+

SW Expert Academy

package DFS_BFS;

import java.util.Scanner;

public class 창용마을무리의개수 {
	static int[] p;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();//테케 입력
		for (int Tc =1 ; Tc <= T; Tc++) {
			 int N=sc.nextInt();//사람 수, 정점의 수
			 int M=sc.nextInt();//관계 수, 간선의 수
			 int[][] arr=new int[M][2];//입력 받을 배열
			 boolean[] check=new boolean[N+1];//사람의 번호 수만큼의 불린 배열
			 for (int i = 0; i < M; i++) {
				arr[i][0]=sc.nextInt();//시작의 정점
				arr[i][1]=sc.nextInt();//끝의 정점
			}//입력 끝
			 
			 p=new int[N+1];
			 for (int i = 1; i <= N; i++) {
				p[i]=i;
			}//makeset
			 
			 for (int i = 0; i < M; i++) {
				int px=findset(arr[i][0]);
				int py=findset(arr[i][1]);
				
				if (px!=py) {
					union(px,py);
				}
			}
			for (int i = 1; i <= N; i++) {
				check[findset(i)]=true;
				//이 부분이 제일 중요
				//p[]은 마지막에 {0,1,1,1,1,1,3}으로 끝난다.
				//그래서 원래 했던데로 check[p[i]]=true라고 하면
				//1,3에서 true값이 나오게 돼 답이 2가 나온다.
				//원래의 알고리즘과 조금 다르게 생각을 좀 더 해서
				//각 숫자의 부모 원소를 찾아주기 위해 findset(i)를 check배열 안에 넣어줘
				//각 숫자의 부모 원소로 찾아가주게 한 값들을 true로 하면 다 1이 나오게 되어
				//모든 값들이 true가 된다.
				//그리고 최소신장트리를 찾는 문제가 아니기 때문에
				//pick값을 세주며
				//pick값이 정점-1이 됐을 때 break;를 걸어주는 것을 넣어주면 안된다.
			}
			int count=0;
			for (int i = 1; i <= N; i++) {
				if (check[i]) {
					count++;
				}
			}
			System.out.println("#"+Tc+" "+count);
		}
	}

	private static void union(int x, int y) {
		p[y]=x;
	}

	private static int findset(int x) {
		if (x!=p[x]) {
			p[x]=findset(p[x]);
		}
		return p[x];
	}
}

크루스칼 알고리즘을 익히고 그거랑 완전 똑같은 방식으로는 풀면 안되고 그것을 완전히 이해한 뒤 풀 수 있는 문제다. 일단 크루스칼 알고리즘을 익히는 것이 제일 중요하고, 중간에 제일 중요하다고 한 부분을 이해하기 위해 find union알고리즘을 잘 익히고 크루스칼 알고리즘을 완전 익혀 차이점을 아는 것이 중요하다.