[알고리즘] 유니온-파인드 (자바)

[알고리즘] 유니온-파인드 (자바)

유니온 파인드란?

말 그대로 union-find 알고리즘을 의미합니다.(주로 트리구조를 이용합니다.)

즉 집합-찾기 입니다.

같은 말로 disjoint-set이 있습니다.

사용 이유

1) 서로 다른 2개의 노드를 입력받아서 그 노드들을 합치거나,

2) find함수로 서로 다른 2개의 노드가 현재의 그래프에 속하는지 판별할 수 있습니다.

예제 코드

find 코드

public static int find(int x) { if( x == result[x]) { return x; } return result[x] = find(result[x]); }

union 코드

public static void union(int x, int y) { x = find(x); y = find(y); if( x != y ) { result[x] = y; } }

p.s

같이 풀어보면 좋은 백준 문제 번호 : 10775

728x90

반응형

from http://kjs-dev.tistory.com/157 by ccl(A) rewrite - 2021-10-19 04:01:12