팀 결성

 

 

문제

- 학생들이 0번부터 N번까지 존재한다. 팀 합치기, 같은 팀 여부 확인 연산을 실행하라.

- 데이터가 주어질때, 앞자리가 0이면 합치기 연산, 1이면 같은 팀 확인 여부 연산을 실행한다.

 

구현

- 서로소 집합 알고리즘

- 경로 최적화

 

 

코드

public class Question1 {
    public static void main(String[] args){
        int[][] data = {
            {0, 1, 3}, {1, 1, 7}, {0, 7, 6}, {1, 7, 1},
            {0, 3, 7}, {0, 4, 2}, {0, 1, 1}, {1, 1, 1}
        };
        int[] parents = new int[8];
        for(int i=0; i<8; i++){
            parents[i] = i;
        }
        for(int[] now : data){
            if(now[0] == 0){
                int parent1 = find_parent(parents, now[1]);
                int parent2 = find_parent(parents, now[2]);
                parents[parent1] = (parent1 > parent2) ? parent2 : parent1;             
                parents[parent2] = (parent1 > parent2) ? parent2 : parent1;
                continue;
            }
            if(find_parent(parents, now[1]) == find_parent(parents, now[2])){
                System.out.println("YES");
            }
            else{
                System.out.println("NO");
            }
        }
    }
    public static int find_parent(int[] parents, int node){
        if(node != parents[node]){
            parents[node] = find_parent(parents, parents[node]);
        }
        return parents[node];
    }
}