백준 [자바 java] 1717번 : 집합의 표현

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

1717번: 집합의 표현

 

이 문제는 유니온파인드를 사용하여 풀었다. 옛날에는 유니온파인드가 복잡하고 별로라고 생각했는데, 난이도가 올라갈수록 집합문제에 이 알고리즘을 안쓰면 시간초과, 메모리초과 없이 문제를 풀 수가 없다. 

처음에는 find함수에서 return할 때 재귀로 받은 값을 union[k]에 넣는 것을 생략했는데, 이랬더니 시간초과가 났다.

앞으로는 귀찮다고 생략하지 말자.

 

풀이방법

• 전역변수로 union배열 생성
• find함수를 만든다.(union[k] == k일 때까지 재귀로 돌려준다)
• 메인에서 요소의 갯수만큼 배열 할당해주고, union에 각각 본인의 수 넣어준다.
• m번 세 수를 입력받는다.
• 이때 첫번째 수가 1이면 두번째 , 세번째 수를 find해주어 값을 비교하고 두 수가 같으면 같은 집합이라는 의미이므로 yes를, 아니면 no를 출력한다.
• 0이면 b와 c를 find 해주고 이 들중 작은 수의 union에 큰 수를 넣어준다.

 

풀이코드

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


public class Main {

    static int[] union;

    static int find(int k){
        if(union[k] == k){
            return k;
        }
        else return union[k] = find(union[k]);
    }


    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());

        union = new int[n+1];

        for(int i = 0;i<=n;i++){
            union[i] = i;
        }

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

            if(a == 1){
                if(find(b) == find(c)){
                    sb.append("YES").append("\n");
                }
                else{
                    sb.append("NO").append("\n");
                }
            }
            else{
                int first = find(b);
                int second = find(c);
                if(first < second) union[first] = second;
                else union[second] = first;
            }
        }

        System.out.println(sb);

    }
}