[백준] Gold V. 집합의 표현

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

 

알고리즘 유형

• 그래프
• 유니온 파인드

 

풀이

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

public class boj1717 {
    static int n, m;
    static int [] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        parent = new int[n + 1];
        for(int i = 1; i <= n; i++){
            parent[i] = i; // i값으로 초기화
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int check = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (check == 0) {
                union(a,b);
            }

            else if (check == 1) {
                check(a,b);
            }
        }

    }

    public static void check(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    public static int find(int n) {
        if (parent[n] == n) { // 배열 인덱스와 값이 같다면 해당 값 리턴
            return n;
        }
        // System.out.println("find: " + find(parent[n]));
        int m = find(parent[n]);
        parent[n] = m;
        return m;
    }
}

 

 

회고

 

크루스칼 알고리즘과 프림 알고리즘을 풀기 전에, 유니온 파인드 알고리즘에 대한 이해가 선행되어야 했기 때문에 찾아서 공부했다. 

 

유니온 파인드는 언제 사용될까?

서로 다른 2개의 원소가 같은 집합인지 여부를 체크할 때 사용된다. 유니온 파인드에는 union 메서드와 find 메서드가 존재하는데, 이 두개를 이해하는게 중요하다.

 

처음에 입력을 받을 때 1차원 배열에 각 노드의 번호를 값으로 입력 받는다.

 

int [] parent

1	2	3	4	5	6
1	2	3	4	5	6

find

특정 노드 n에 대해서 대표 노드를 리턴하는 함수

    public static int find(int n) {
        if (parent[n] == n) { // 배열 인덱스와 값이 같다면 해당 값 리턴
            return n;
        }
        // System.out.println("find: " + find(parent[n]));
        int m = find(parent[n]);
        parent[n] = m;
        return m;
    }

 

배열의 인덱스와 값이 같다면 바로 리턴해주면 된다. ex) parent[1] = 1

 

 

하지만, 노드가 이렇게 연결되어 있다면,

1	2	3
1	1	2

 

이런식으로 배열이 표현될 것이다. (A,B,C가 1,2,3이라고 가정)

 

여기서 1과 3의 연결 여부는 어떻게 알 수 있을까? 

 

재귀적으로 3의 대표 노드인 2를 리턴하고, 또 2는 대표 노드인 1을 리턴해서 최종적으로 1과 3이 연결되어 있음을 확인할 수 있다.

 

union

각 노드가 속한 집합을 하나로 합치는 함수

 

public static void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[b] = a;
    }
}

 

앞서 선언한 find 함수를 통해서 값을 가져오고, 두 개의 값이 다르다면 대표 노드를 바꿔준다.

 

일반적으로, 더 작은 쪽이 대표 노드가 된다.