[JAVA] 유니온 파인드(Union-Find)

유니온 파인드

모든 노드가 같은 부모를 가지면 같은 집합이라는 것!

이러한 문제는 유니온 파인드(Union-Find)를 이용하여 풀 수 있습니다.
이 개념을 이해하고 부모 값(대푯값)을 찾아야합니다.

• 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다
• 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어진다.

전역 변수

int n = 도시의 수
int parent[] = 그룹의 대표를 나타내는 배열

함수

void main
입력을 받고 2차원 배열을 읽어서 도시를 연결해줍니다.
여행할 도시를 입력받고 각 도시의 대표를 비교하여 모두 같으면 "YES" 그렇지 않으면 "NO"를 출력합니다.
(union 호출)

void union

• 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집한 연산과 같다.

두 개의 파라미터를 서로 연결합니다. 각 도시의 그룹 대표를 p1, p2로 구합니다.
그리고 그룹의 가장 작은 값이 그룹 대표가 되므로 작은 값을 기준으로 넣어줍니다.
이때 주의할 점은 대푯값을 기준으로 작업을 합니다. parent[p1] = p2처럼 대표 값을 조작합니다.

int find

• 하나읜 원소가 어떤 집합에 속해있는지를 판단한다.

재귀를 통해 구현했으며 재귀 과정에서 최적화를 거칩니다. 종료 시점은 파라미터의 대표가 곧 자신일 때(그룹의 가장 작은 수)입니다.

union && find

    //x의 집합 찾기 : x의 대표자 찾기
    private static int find(int x) {
        if (parents[x] == x) return x; // 현재 노드의 부모가 존재하지 않는경우(현재 노드가 루트노드) 자기 자신 반환
        return parents[x] = find(parents[x]); // 현재 노드의 부모 노드가 존재한다면 재귀를 통해 루트노드를 찾아 반환
    }

    //x, y 두 집합 합치기 - 부모 노드(루트 노드) 가 같다면 두 노드의 부모 노드를 같게 만든다. 
    private static void union(int x, int y) {
        int p1 = find(x);
        int p2 = find(y);

        if(x == y) return; // x와 y의 부모 노드가 같다면 두 노드는 연결되어 있다.

        // 부모 노드와 같게 만드는 union 작업
        if (p1 < p2) {  //더 작은(우선순위가 높은) 노드를 부모 노드로 선정한다. 
            parents[p1] = p2;
        } else {
            parents[p2] = p1;
        }
    }

정답

https://www.acmicpc.net/problem/1976

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main { //유형: 그래프 , 메모리제한: 128MB, 시간 제한: 2초
    static int n, m;
    static int[] parents;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine()); // 도시 수
        m = Integer.parseInt(br.readLine()); // 여행 계획 속한 도시
        parents = new int[n + 1];
        for (int i = 1; i <= n; i++) parents[i] = i;

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (num == 1) union(i, j);  // 1 : 연결, 0 : 연결X
            }
        }

        String res = "YES";
        st = new StringTokenizer(br.readLine());
        int parent = Integer.parseInt(st.nextToken());
        for (int i = 1; i < m; i++) {
            int now = Integer.parseInt(st.nextToken());
            if (find(parent) != find(now)) {
                res = "NO";
                break;
            }
        }
        System.out.println(res);
    }

    //x의 집합 찾기 : x의 대표자 찾기
    private static int find(int x) {
        if (parents[x] == x) return x; // 현재 노드의 부모가 존재하지 않는경우(현재 노드가 루트노드) 자기 자신 반환
        return parents[x] = find(parents[x]); // 현재 노드의 부모 노드가 존재한다면 재귀를 통해 루트노드를 찾아 반환
    }

    //x, y 두 집합 합치기 - 부모 노드(루트 노드) 가 같다면 두 노드의 부모 노드를 같게 만든다.
    private static void union(int x, int y) {
        int p1 = find(x);
        int p2 = find(y);

        if (x == y) return; // x와 y의 부모 노드가 같다면 두 노드는 연결되어 있다.

        // 부모 노드와 같게 만드는 union 작업
        if (p1 < p2) { 
            parents[p2] = p1;
        } else {
            parents[p1] = p2;
        }
    }
}