[백준] 1717: 집합의 표현 - JAVA

in Algorithm on 자료 구조

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

풀이

자료구조, 서로소집합 문제.

집합들이 있고, 합집합연산과 서로 같은 집합인지 확인하는 연산이 있다.

배열을 집합의 개수만큼 만들고 자신의 번호로 초기화 한다.

자신의 그룹을 찾는 함수, 그룹을 합치는 함수, 같은 그룹인지 확인하는 함수 3가지를 구현해야 한다.

자신의 그룹을 찾는 findGroup 함수에서는 배열의 값을 findGroup의 결과값으로 갱신하면서 어떤 그룹에 속해있는지 찾는다.

그룹을 합치는 grouping 함수에서는 findGroup을 한 결과들을 이용해 두 집합을 하나의 그룹으로 묶어준다.

같은 그룹인지 확인하는 check 함수에서는 마찬가지로 findGroup을 한 결과가 서로 같은지 여부를 판단한다.

메모리: 58372KB

시간: 744ms

언어: Java 11

코드

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

public class Main {
    static int[] arr;

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

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

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

            if (type == 0) {
                grouping(a, b);
            } else if (type == 1) {
                sb.append(check(a, b)? "YES" : "NO").append("\n");
            }
        }

        System.out.println(sb);
    }

    private static int findGroup(int a) {
        if (a == arr[a]) {
            return a;
        } else {
            return arr[a] = findGroup(arr[a]);
        }
    }

    private static void grouping(int a, int b) {
        int pa = findGroup(a);
        int pb = findGroup(b);

        if (pa < pb) {
            arr[pb] = pa;
        } else {
            arr[pa] = pb;
        }
    }

    private static boolean check(int a, int b) {
        int pa = findGroup(a);
        int pb = findGroup(b);

        if (pa == pb) {
            return true;
        } else {
            return false;
        }
    }
}