[HackerRank] Components in a graph(Java, union-find)

## 접근방법

---

우선 이 문제는 처음 접근 방법으로는 런타임 에러를 받았다. 런타임 에러는 인덱스 초과, 스택 오버 플로우 등의 이유로 발생한다. 스택 오버 플로우에 접근했었던 접근 방법에 대해서 알아보자.

 

 

스택 오버 플로우가 발생했던 접근 방법은 노드들을 전체 탐색하는 것이다. 물론 방문했던 노드들을 다시는 방문안하도록 체크하는 배열을 사용해도 스택 오버 플로우가 발생한다. 각 노드들에서 나머지 노드들을 모두 방문할 수 있으므로 시간복잡도는 N * N이 된다.

 

 

우선, 스택 오버 플로우가 발생하지 않으려면 함수의 재귀적 호출을 줄이거나 없애야 한다. 함수의 재귀적 호출을 없애는 것으로 문제를 풀어보자. 

 

 

그래프에서 Union-Find라는 개념은 그래프에서 흔히 사용된다. 두 그래프를 합치고, 각 그래프의 부모 노드을 저장하고 있는 것이다. 이렇게 되면 시간 복잡도는 쿼리의 수 * N(노드의 수)가 되므로 시간 복잡도도 줄어들었다. 

 

 

문제에서 요구하는 것은, 그래프의 최대 길이와 최소 길이이다. Union이 발생할 때, 각 루트 노드에 합쳐진 길이를 저장해야 한다. 루트 노드에만 합쳐진 길이를 저장하므로, 나중에 결과를 얻을 때도 루트 노드들에서만 탐색이 이루어져야 한다.

 

 

Union-Find에 대해서 정확히 이해하고 있다면, 쉽게 코드가 이해될 것이다.

 

 

## 해설코드

---

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
class Result {
 
    /*
     * Complete the 'componentsInGraph' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts 2D_INTEGER_ARRAY gb as parameter.
     */
    
    static int[] root;
    static int[] cnt;
    static int minAnswer = 30000;
    static int maxAnswer = 0;
    
    static int find(int node){
        if(root[node] == node)
            return node;
        else 
            return root[node] = find(root[node]);
    }
    
    static void union(int node1 ,int node2){
        int root1 = find(node1);
        int root2 = find(node2);
        
        int sumLen = cnt[root1] + cnt[root2];
        
        if(root1 == root2)
            return;    
            
        root[root2] = root[root1];
        
        cnt[root1] = sumLen;
        cnt[root2] = sumLen;
    }
 
    public static List<Integer> componentsInGraph(List<List<Integer>> gb) {
    // Write your code here
        List<Integer> result = new ArrayList<>();
    
        int N = 15000;
        root = new int[2 * N + 1];
        cnt = new int[2 * N + 1];
        
        for(int i = 1; i <= 2 * N; i++){
            root[i] = i;
            cnt[i] = 1;
        }
        
        for(int i = 0; i < gb.size(); i++){
            int left = gb.get(i).get(0);
            int right = gb.get(i).get(1);
            
            union(left, right);
        }
        
        for(int i = 1; i <= N; i++){
            int ret = cnt[find(i)];
            
            if(ret != 1){
                minAnswer = Math.min(minAnswer, cnt[find(i)]);
                maxAnswer = Math.max(maxAnswer, cnt[find(i)]);
            }
        }
        
        result.add(minAnswer);
        result.add(maxAnswer);
        return result;
    }
 
}
 
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        int n = Integer.parseInt(bufferedReader.readLine().trim());
 
        List<List<Integer>> gb = new ArrayList<>();
 
        for (int i = 0; i < n; i++) {
            String[] gbRowTempItems = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
 
            List<Integer> gbRowItems = new ArrayList<>();
 
            for (int j = 0; j < 2; j++) {
                int gbItem = Integer.parseInt(gbRowTempItems[j]);
                gbRowItems.add(gbItem);
            }
 
            gb.add(gbRowItems);
        }
 
        List<Integer> result = Result.componentsInGraph(gb);
 
        for (int i = 0; i < result.size(); i++) {
            bufferedWriter.write(String.valueOf(result.get(i)));
 
            if (i != result.size() - 1) {
                bufferedWriter.write(" ");
            }
        }
 
        bufferedWriter.newLine();
 
        bufferedReader.close();
        bufferedWriter.close();
    }
}