[java] 백준 1717번 문제(집합의 표현)

원본 링크 : https://www.acmicpc.net/problem/1717

---

문제설명

 

 

소스코드

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

public class Boj_1717
{
    static int[] parent;

    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 n = Integer.parseInt(st.nextToken()); // 원소 수
        int m = Integer.parseInt(st.nextToken()); // 연산 수

        parent = new int[n + 1];
        for (int i = 1; i < n + 1; ++i) parent[i] = i; // 자기 자신으로 초기화

        for (int i = 0; i < m; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            int nodeA = Integer.parseInt(st.nextToken());
            int nodeB = Integer.parseInt(st.nextToken());

            if (cmd == 0) union(nodeA, nodeB);
            else
            {
                if (find(nodeA) == find(nodeB)) sb.append("YES").append(System.lineSeparator());
                else sb.append("NO").append(System.lineSeparator());
            }
        }

        System.out.print(sb);
    }

    static int find(int value)
    {
        if (parent[value] != value) parent[value] = find(parent[value]);
        return parent[value];
    }

    static void union(int a, int b)
    {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB)
        {
            if (rootA < rootB) parent[rootB] = rootA;
            else parent[rootA] = rootB;
        }
    }
}

 

설명

• 최대 원소의 개수와 질의 개수를 고려해봤을 때 경로 압축이 필요한 전형적인 유니온 파인드 문제이다.
• 유니온 파인드에 대한 설명은 아래의 링크로 확인 가능하다.

2025.05.06 - [자료구조 & 알고리즘/알고리즘] - [java] 유니온 파인드(Union-Find)

[java] 유니온 파인드(Union-Find)