백준1717 문제 풀이

Union-Find 기본 문제이고 골드5로 난이도가 낮은 편이라고 생각합니다.

이전 포스트의 union-find의 기본 개념만 알고 있다면 쉽게 풀 수 있습니다.

0~N까지의 서로소 집합이 있고 merge, find 함수 그리고 두 그룹이 같은 그룹에 속하는지 체크하는 함수만 있으면 됩니다.

두 그룹이 같은 그룹인지 체크는 root 노드가 같은지 체크하면 됩니다.

 

아래는 풀이 코드입니다.

package backjoon;

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

public class Backjoon1717 {
    public static int parents[], ranks[], N, M;
    public static final String NO = "NO";
    public static final String YES = "YES";

    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());
        parents = new int[N+1];
        ranks = new int[N+1];
        for(int i = 0; i<=N; i++){
            parents[i] = i;
        }
        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) {
                merge(a,b);
            }else {
                System.out.println(isSameGroup(a,b));
            }
        }
        br.close();
    }

    private static String isSameGroup(int a, int b) {
        int aParent = find(a);
        int bParent = find(b);
        if(aParent == bParent)
            return YES;
        else
            return NO;
    }

    private static int find(int x) {
        if(parents[x] == x) {
            return x;
        }
        return parents[x] = find(parents[x]);
    }
    private static void merge(int a, int b) {
        int aParent = find(a);
        int bParent = find(b);
        if(aParent != bParent) {
            if(ranks[aParent] < ranks[bParent]) {
                parents[aParent] = bParent;
            }else {
                if(ranks[aParent] == ranks[bParent]) {
                    ranks[aParent]++;
                }
                parents[bParent] = aParent;
            }
        }
    }
}