[백준 Java]1717 집합의 표현

<링크>

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

1717번: 집합의 표현

 

<풀이>

크루스칼 알고리즘 풀이에 사용되는 union과 findParent 메서드를 생성하여 해결하였다

먼저 초기에 각 노드들의 부모를 자기 자신으로 초기화한다.

명령으로 union을 하라고 들어온다면 먼저 a, b의 가장 조상 노드를 찾는다

그 후에 두 조상노드 값 중 더 작은 값으로  조상 노드를 갱신하면 union 된다.(마치 트리구조 같이)

명령으로 print를 하라고 하면 a, b의 조상 노드를 찾고 그 값이 일치하면 YES, 일치하지 않으면 NO를 출력하면 된다. 

 

<코드>

package 백준.graph;

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

public class boj_1717_집합의표현 {
    private static final int UNION = 0;
    private static final int PRINT = 1;

    private static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(st.nextToken());
        int line = Integer.parseInt(st.nextToken());
        parents = new int[size + 1];

        /*init*/
        for (int i = 0; i <= size; i++) {
            parents[i] = i;
        }


        while (line-- > 0) {
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (cmd == UNION) {
                unionParens(a,b);
            }
            else if (cmd == PRINT) {
                if (findParent(a)== findParent(b))
                    sb.append("YES");
                else sb.append("NO");
                sb.append("\n");
            }
            else {
                throw new IllegalArgumentException();
            }
        }
        System.out.println(sb);
    }

    static int findParent(int a){
        if(a==parents[a]) return a;
        return parents[a] = findParent(parents[a]);
    }

    static void unionParens(int a,int b){
        //최고 조상을 수정해야함
        a = findParent(a);
        b = findParent(b);
        if(a==b) parents[b]=a;
        else parents[a]=b;
    }

}