백준 18116 (로봇 조립) - java

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

 

문제

성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 부품인지 알 수 있다. 그래서 성규는 호재의 지시에 따라 부품들을 정리하기로 하였다.

부품들은 1부터 10^6까지의 정수로 표현된다. 그리고 부품 i가 속한 로봇은 robot(i)라고도 표현한다. 예를 들어, 부품 11과 부품 22가 로봇 A의 부품이라고 알고 있는 경우, robot(11)은 로봇 A를 의미하고, robot(22)도 로봇 A를 의미한다.

서로 다른 로봇은 공통 부품을 가지지 않는다. 즉 어떤 부품이 로봇 A의 부품이라면, 로봇 B의 부품은 될 수 없다.

호재는 2가지 지시를 한다.

• 서로 다른 부품 2개를 말해주며, 두 부품은 같은 로봇의 부품이라는 정보를 알려준다.
• 부품 i에 대해서, 지금까지 알아낸 robot(i)의 부품이 몇 개냐고 물어본다.

초기에는 부품에 대한 정보가 존재하지 않는다.

 

유형 : Union - Find

 

접근 방식

• 로봇의 부품들이 겹치는 경우가 없다 + 부품들로 로봇을 부른다 -> 분리집합으로 접근해야 한다.

전체 코드

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

public class Main {

    static int n;

    static int[] root = new int[1000_001];

    static HashSet<Integer>[] set = new HashSet[1000_001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();


        for(int i = 1 ; i <= 1000_000 ; i++){
            root[i] = i;
            set[i] = new HashSet<>();
            set[i].add(i);
        }

        n = Integer.parseInt(st.nextToken());

        int tmpRoot = 0;

        for(int i = 1 ; i <= n ; i++){
            st = new StringTokenizer(br.readLine()," ");

            String what = st.nextToken();

            if(what.equals("I")){
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                if(find(v1) != find(v2)){
                    union(v1,v2);
                }
            }else{
                int v = Integer.parseInt(st.nextToken());

                tmpRoot = find(v);

                sb.append(set[tmpRoot].size()+"\n");
            }
        }
        System.out.print(sb);

        br.close();
    }

    static int find(int x){
        if(x == root[x])
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y){
            root[y] = x;
            set[x].addAll(set[y]);
        }else{
            root[x] = y;
            set[y].addAll(set[x]);
        }
    }
}