[JAVA] 백준 24391번 - 귀찮은 해강이

24391번: 귀찮은 해강이 (acmicpc.net)

24391번: 귀찮은 해강이

package baekjoon;
import java.util.*;
import java.io.*;

public class b24391 {
	static int parent[];
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		parent = new int[n+1];
		
		for(int i = 1 ; i <= n ;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());
			Union(a, b);
		}
		st = new StringTokenizer(br.readLine());
		int a[] = new int[n];
		for(int i = 0 ; i < n ; i++)
		{
			a[i] = Integer.parseInt(st.nextToken());
		}
		int cnt = 0;
		for(int i = 0 ; i < n-1 ; i++)
		{
			if(Find(a[i]) != Find(a[i + 1]))
				cnt++;
		}
		bw.write(cnt+"");
		bw.close();
	}
	static public int Find(int a)
	{
		if (a == parent[a])
			return a;
		return parent[a] = Find(parent[a]);
	}

	public static void Union(int a, int b)
	{
		int pa = Find(a), pb = Find(b);
		parent[pa] = pb;
	}
}

혼자 해보고 싶어서 열심히 하다가 포기하고 구글링 하니까

유니온파인드?를 써야하는 문제더라구요

 

연결된 것들을 다 하나로 연결하고 맨 위에 애를 루트노드로 하는 그런 느낌인데

지금 완전 제꺼가 된 느낌은 아니라 

[Algorithm] 유니온 파인드(Union-Find)란?? python에서 구현하기 (tistory.com)

[Algorithm] 유니온 파인드(Union-Find)란?? python에서 구현하기

이 선생님 설명이 기가 막힙니다