문제사항

골드 5단계 문제였다.

유니온 파인드의 기본이 되는 문제이다.

유니온 파인드(Union-Find)란?

• 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있다.

• 상호 배타적 집합(Disjoint-set)이라고도 한다.

• 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

• 2가지 연산으로 이루어져 있다.

  • Find : x가 어떤 집합에 포함되어 있는지 찾는 연산

  • Union : x와 y가 포함되어 있는 집합을 합치는 연산

위와 같이, 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만든다.

i : 노드번호, P[i] : 부모 노드 번호 를 의미하며, 즉 자기 자신이 어떤 부모에 포함되어 있는지를 의미한다.

Parent[i] = i

Union(1,2); Union(3,4) 를 해주어 위와 같이 노드를 연결해보자

2번째 인덱스에 '1'이 들어가고, 4번 인덱스에 '3'이 들어간다.

부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합친다.

이것을 Union 이라고 말할 수 있다.

위와 같이 1, 2, 3이 연결될 때는 위와 같이 표현된다.

1과 3은 부모가 다르기 때문에 '1과 3이 연결되었는지' 파악하기 힘들기 때문에 재귀함수가 사용된다.

3의 부모인 2를 먼저 찾고, 2의 부모인 1을 찾아, 결과적으로 3의 부모는 1이 되는 것을 파악하는 것이다.

위 세 가지 노드 1,2,3의 부모는 모두 1이기 때문에 같은 그래프에 속한다는 것을 알 수 있다.

이제 알고리즘을 익혔으니 문제를 풀어보자.

union 메서드 : 합집합 연산

isSameParent : 교집합 여부 판단

참고로 입력 값이 0일 때는 합집합 연산, 1일 땐 교집합 여부를 판단하는 것을 잊지 말자.

알고리즘 분류

1. 그래프 (유니온 파인드)

코드

import java.io.*;
import java.util.*;

public class Main {

    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());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

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

            if (num == 0) {
                union(a, b);
            } else if (num == 1) {
                sb.append(isSameParent(a, b) ? "YES" : "NO").append("\n");
            } else {
                continue;
            }
        }
        System.out.println(sb);
    }

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

    static void union(int x, int y) {
    //합집합
        x = find(x);
        y = find(y);
        
		// 부모를 합칠 때에는 일반적으로 더 작은 쪽으로 합쳐짐
        if (x != y) {
            if (x < y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }

    public static boolean isSameParent(int x, int y) {
    //교집합
        x = find(x);
        y = find(y);

        if (x == y) {
            return true;
        }
        return false;
    }
}

출처

[백준] 집합의 표현