[BOJ_18116] 로봇 조립

설명

---

우선 코드 자체는 Union-find를 활용하였다. 그 이유는 문제 설명 중 ( 부품 11과 부품 22가 로봇 A의 부품이라고 알고 있는 경우, robot(11)은 로봇 A를 의미하고, robot(22)도 로봇 A를 의미한다. ) 이와 같이 같은 집합의 로봇끼리는 같은 로봇으로 참고 하기 때문이고 그렇다고 해서 전체 집합의 로봇 부품들이 모든 같은 로봇을 참조하지는 않기 때문에 합집합 끼리 묶어 줄 수 있는 것이 필요하였기 때문이다. 다만, 10^6으로 parent 배열이 N + 1개를 의미하지 않기 때문에 root에 따른 동일한 부품 탐색 시 꽤나 탐색 범위가 커질 수 있다. 10^6 * 10^6과 같은 최악의 경우의 수가 나올 수 있기 때문에 단순히 for문으로 짜면 처음부터 끝까지 모두 탐색해서 절대 문제를 풀 수 없다. 

 

따라서, 처음 parent 탐색 시에 바로 해당 root 범위의 size를 카운트를 해버리자는 목적으로 접근해야 한다. root 위치에 같이 연결되는 부품의 최대 갯수를 탐색하자는 개념으로 아래와 같이 코드를 짜서 객체로 연결했는데 차라리 parent, size 배열을 따로 두어서 연동하는 식으로 짜는 것이 다른 사람들이 보았을때 더욱 직관적인 코드가 될 것으로 보인다.

 

코드

---

package BOJ.disjoint_set;

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

public class BOJ_18116 {
    static class Data{ //부품과 자신의 root_index 값을 저장하는 객체
        int root;
        int part;
        public Data (int root, int part){
            this.root = root;
            this.part = part;
        }
    }
    static Data[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(tk.nextToken());
        //초기화 진행
        parent = new Data[1000001];
        for (int i = 1; i < 1000001; i++){
            parent[i] = new Data(i,1); // 첫 위치는 해당 위치의 부품 1이다.
        }

        for (int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine());
            String askChar = tk.nextToken();
            if(askChar.equals("I")){
                int x = Integer.parseInt(tk.nextToken());
                int y = Integer.parseInt(tk.nextToken());
                union(x, y);
            }
            else {
                int a = Integer.parseInt(tk.nextToken());
                System.out.println(parent[find(a)].part);
            }
        }

    }

    private static int find(int a) {
        if(parent[a].root == a){
            return a;
        }
        return parent[a].root = find(parent[a].root);
    }

    private static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX != rootY){
            if(parent[rootX].part > parent[rootY].part){
                parent[rootY].root = parent[rootX].root;
                parent[rootX].part += parent[rootY].part;
            }else{
                parent[rootX].root = parent[rootY].root;
                parent[rootY].part += parent[rootX].part;
            }
        }
    }
}

 

Link

---

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