[알고리즘] Union-Find Algorithm (유니온 파인드 알고리즘)

유니온 파인드 알고리즘이란?

💡유니온 파인드 알고리즘: 상호 배타적 집합, Disjoin-set(서로소 집합) 이라고도 부른다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.

왜 이름이 유니온 파인드인가?

유니온 파인드 알고리즘은 두가지의 연산을 진행한다. 이 연산 과정을 Union, Find라고 부른다.

• Union: 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집한 연산과 같다.
• Find: 하나읜 원소가 어떤 집합에 속해있는지를 판단한다.

크루스칼 알고리즘과 프림 알고리즘을 알기 위해선 유니온 파인드 알고리즘을 알아야 한다.

 

유니온 파인드 예제

오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다. 모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계 가 번호로 표현된 숫자쌍이 주어진다. 만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다. 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다. 학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램 을 작성하세요. 두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.

문제 해설

1번 학생과 2번학생이 친구이며 2번 학생과 3번 학생이 친구. 3번 학생과 4번 학생이 친구이다. 그리고 5번 학생과 6번학생이 친구라면 다음과 같이 그래프로 표현 할 수 있다. 이 두 집합은 공통원소가 없기 때문에 서로소집합 즉 Disjoin-set이라 볼 수 있다. 이것을 판별하는 알고리즘이 Union Find 알고리즘이다.

입력 예제

9 7
1 2
2 3
3 4
1 5
6 7
7 8
8 9
3 8 // 친구인지 검사하는 입력 예제

 

출력 예제

NO

 

1) 우선 배열이 필요하다. unf 배열의 인덱스는 학생 번호에 해당하며 배열의 값은 집합의 번호와 같다. 아직 어떤 집합에 속해있는지 알지 못하기 때문에 인덱스 별로 초기화 해준다.

2) 처음 들어온 값이 1과 2이다 이들은 인접한 정점이니 같은 집합임을 명시해준다.

3) 다음 들어온 값은 2와 3 그리고 3과 4이다. 2번 과정에서 처리했던 방법과 똑같이 같은 집합임을 명시해준다.

4) 다음은 1과 5이다. 1부터 4는 서로 엮여있으며, 공통 집합이다. 이때 4에 5만 엮여주면 공통집합이 되므로 다음과 같이 인덱스 4의 값을 바꾸어준다.

5) 위와 같은 방법으로 하면 1과 5의 연관관계를 살필 때, 1에서 2, 2에서 3 ... 4에서 5로 각 과정을 거쳐가야 한다. 이 경로를 단축 시키는 방법이 있다. 밑의 사진과 같이 그래프를 처리한다면 불필요한 정점을 거치지 않아도 된다.

6) 이와 같은 과정을 통해 모든 정점을 검사하면 이와 같은 답이 나오게된다.

완성 코드

import java.util.*;
class Main {
	static int[] unf;
	public static int Find(int v){
		if(v==unf[v]) return v;
		else return unf[v]=Find(unf[v]);
	}
	public static void Union(int a, int b){
		int fa=Find(a);
		int fb=Find(b);
		if(fa!=fb) unf[fa]=fb;
	}
	public static void main(String[] args){
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		unf=new int[n+1];
		for(int i=1; i<=n; i++) unf[i]=i;
		for(int i=1; i<=m; i++){
			int a=kb.nextInt();
			int b=kb.nextInt();
			Union(a, b);
		}
		int a=kb.nextInt();
		int b=kb.nextInt();
		int fa=Find(a);
		int fb=Find(b);
		if(fa==fb) System.out.println("YES");
		else System.out.println("NO");		
	}
}

 

Reference

자바 알고리즘 문제풀이 코테대비-인프런