-
[알고리즘 정리] Union-Find(유니온 파인드)Development/Algorithm 2020. 5. 3. 17:29
다룰 내용
- 서로소 집합이란 무엇인가?
- 상호 배타 집합을 표현하는 방법
- Union Find 구현
서로소 집합(Disjoint-set)이란?
서로소 또는 상호 배타 집합들은 서로 중복되는 원소가 없는 집합을 말합니다.
상호 배타 집합을 표현하는 방법
- 연결 리스트로 구현
- 트리로 구현
상호 배타 집합 연산
- Make-set(x) : 집합을 만드는 동작입니다.
- Find-set(x) : x가 속한 집합을 찾는 동작입니다.(이때 해당 원소의 대표자를 반환합니다.)
- Union(x, y) : 두 집합의 원소를 주고 합치는 동작입니다.
상호 배타 집합 - 연결리스트 구현
- 같은 집합의 원소들은 하나의 연결리스트로 관리합니다.
- 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 생각해봅니다.
- 따라서 각 원소는 집합의 대표 원소를 가리키는 링크를 갖도록 구현합니다.
상호 배타 집합 - 트리 구현
- 같은 집합의 원소들은 하나의 트리로 관리하게 됩니다.
- 자식 노드가 부모 노드를 가리키며 루트 노드가 그 트리의 대표자가 되도록 구현합니다.
Union Find 구현
저는 트리 방식으로 Union Find를 구현해보았습니다. union을 호출하면 union 메소드 내부에서 find 메소드를 호출하여 각 원소의 가장 최상위 노드를 반환받습니다. 그리고 받은 둘의 부모 노드가 다르다면 합치고 같다면 합치지 않는 과정을 수행합니다. 같지 않다면 한 쪽의 부모 노드를 다른 쪽의 노드로 셋팅해줍니다.
그냥 단순히 한 쪽의 노드를 다른 쪽 노드의 자식으로 붙여도 무방하나, 이렇게 할 경우 depth가 깊어짐에 따라 부모 노드를 찾는 과정에 시간이 많이 소요됩니다. 따라서 합쳐질 노드의 부모를 그 트리의 root 노드로 설정을 해줍니다. 이렇게 하면 path 압축이 일어나 부모를 찾아 올라가는 시간을 단축할 수 있습니다.
package basic; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class UnionFind { public static int N, parents[]; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); parents = new int[N]; int cnt = Integer.parseInt(br.readLine()); Arrays.fill(parents, -1); while(cnt-- > 0) { String input[] = br.readLine().split(" "); int x = Integer.parseInt(input[0]); int y = Integer.parseInt(input[1]); if(union(x, y)) { System.out.println("합치기 성공"); } else { System.out.println("이미 같은 집합임."); } } for (int i = 0; i < N; i++) { System.out.println(find(i)); } } private static int find(int x) { if(parents[x] < 0) return x; return parents[x] = find(parents[x]); } private static boolean union(int x, int y) { int xRoot = find(x); int yRoot = find(y); if(xRoot != yRoot) { // path 압축 parents[yRoot] = xRoot; return true; } return false; } }
'Development > Algorithm' 카테고리의 다른 글
[알고리즘 정리] Dijkstra(다익스트라) (0) 2020.05.03 [알고리즘 정리] Kruskal & Prim(크루스칼과 프림) (0) 2020.05.03 [알고리즘 정리] 조합, 부분 집합 구현 (0) 2020.05.03 [알고리즘 정리] 순열, next_permutation 구현 (0) 2020.04.29 [알고리즘 정리] 재귀 (0) 2020.04.08