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

🔺 문제

1717번: 집합의 표현

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] parent;
    
    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];
        
        // 배열 초기화
        for(int i = 1 ; i <= n ; i++) {
            parent[i] = i;
        }
        
        // 입력 받기
        for(int i = 0 ; i < m ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            
            int uf = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            // UNION 진행
            if(uf == 0) {
                union(a, b);
            }
            else {
                if(checkSame(a, b)) System.out.println("YES");
                else                System.out.println("NO");
            }
        }
    }
    
    // UNION : 집합을 1개로 합침
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) {
            parent[b] = a;
        }
    }
    
    // FIND : 속한 집합의 대표 노드 반환
    public static int find(int a) {
        if(a == parent[a])  return a;
        else                return parent[a] = find(parent[a]); // 경로 압축
    }
    
    // 두 원소가 같은 집합인지 확인
    public static boolean checkSame(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a == b) {
            return true;
        }
        return false;
    }
}

✅ 해결 아이디어
✔ 유니온파인드
- 재귀함수 형태로 경로 압축 효과 → 시간복잡도 : O(1)

 

💥 유의사항

⇨ find 연산 수행 시 :  a가 대표 노드가 아니라면, 대표 노드 값을 find(parent[a])값으로 저장 - 재귀형태

 

---

🔺 다른 풀이들

- union할 때 x<y 인 경우와 그게 아닌 경우로 나눠주심.

[BOJ] 백준 1717번 : 집합의 표현 (JAVA)

---

💬 느낀 점

이해하니 재밌구나...

 

 

1회독	2회독	3회독	4회독	5회독
V	6/22

 

 

(+ 6/22 2회독)

다른 문제에 비하면... 너는 골드 치고 쉽구나.. 고맙다..

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] parent;
    
    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());
        
        parent = new int[n + 1];
        for(int i = 1 ; i <= n ; i++) {
            parent[i] = i;
        }
        
        while(m --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int num = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if(num == 0) {
                union(a, b);
            }
            else {
                sb.append(find(a) == find(b) ? "YES" : "NO").append("\n");
            }
        }
 
        System.out.println(sb);
    }
    
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b)  parent[b] = a;
    }
    
    static int find(int a) {
        if(a == parent[a])  return a;
        return parent[a] = find(parent[a]);
    }
}
 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편

✔ 유니온 파인드

[알고리즘] 유니온 파인드 (Union-Find)