[JAVA] 백준 1717 집합의 표현

 

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

 

문제분석

대충 보면 쉬운 문제다. 물론 그렇게 보이는대로 풀면(나)....바로 시간초과가 난다.

첫 풀이는, Union별로 ArrayList를 관리하면서 직접 합치며 풀려고 했다. 이렇게 하니, 메모리 초과로 인해 문제를 틀렸다(이제보니 메모리도 다른 문제와는 좀 다르게, 128MB만 준다).

 

따라서 다른 풀이로 접근해야 한다. 우리가 원하는건 해당 원소가"어느 집합" 에 속해있는지 이지, 해당 집합에 "어떤 원소들" 이 존재하는지가 아니다. 따라서 부모-자식 관계를 통해 마치 트리처럼 집합 소속 여부를 확인하게 할 수 있다.

 

 

이러한 원리로 소속을 저장한다. 중요한 점은, 부모의 경우는 parent[idx] = idx이고, 병합할때는 병합 기준의 parent 를 꼭 저장해야 한다.

 

코드

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

public class Main {
    public static int[] parent;// 인덱스 n의 부모는 누구인지 저장. 부모가 같으면 같은 union
    
    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());
        parent = new int[N+1]; // 0부터 n까지
        
        for(int i = 0; i < N + 1; i++){// 0부터 N까지 넣어야 함
            parent[i] = i;
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int direct = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if(direct == 0){ // a 집합에 b 집합 편입
                union(a,b);
            }else if(direct == 1){// a와 b가 같은 집합인지(같은 부모인지)
                bw.write(findParent(a) == findParent(b)? "YES" : "NO");
                bw.newLine();
            }
        }
        bw.flush();
        bw.close();
    }

    public static int findParent(int n){
        if(n == parent[n]){
            return n;
        }else{
            return findParent(parent[n]);
        }
    }

    // a집합으로 b집합 편입
    public static void union(int a, int b){
        // b의 parent의 parent를 a의 parent로 초기화(같은 집합)
        int aParent = findParent(a);
        int bParent = findParent(b);
        parent[bParent] = aParent;
    }
}