[BOJ 3780] 네트워크 연결(Java, Union-Find)

www.acmicpc.net/problem/3780

3780번: 네트워크 연결

## 접근

---

• 이 문제는 대놓고 Union-Find 문제이다. Union-Find의 재귀호출 방식을 이용해서, 코드를 응용할 수 있는지 묻고 있다.
  
  
  
  
• 병합 과정의 2.를 이해가 쉽지 않았다. A 클러스트의 새로운 센터가 j가 된다는 것을 의미하는 내용인데, 처음 읽을 때는, B 클러스터의 별도의 센터가 존재할 수도 있다고 생각했다. 
  
  
  
  
• Union시에 I의 새로운 센터를 J로 만들어 주고, I의 거리를 갱신해준다. 기업 I와 현재 I의 센터까지의 거리를 출력할 때는 Find 연산을 통해서, 연결된 모든 값의 거리를 갱신해줘야 한다.

 

 

 

## 해설코드

---

import java.util.*;
import java.io.*;
import java.lang.*;
 
public class Main{
    static BufferedReader br;
    static BufferedWriter bw;
    static int T, I, J, N;
    static int[] root;
    static int[] dis;
    static String str;
 
    static int find(int x){
        if(x == root[x])
            return x;
        else{
            int tmp = find(root[x]);
            dis[x] += dis[root[x]];
            root[x] = tmp;
            
            return tmp;
        }
    }
    
    static void union(int x, int y){
        dis[x] = Math.abs(x - y) % 1000;
        root[x] = y;
    }
    
     public static void main(String []args) throws java.lang.Exception{
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        T = Integer.valueOf(br.readLine());
        
        for(int i = 1; i <= T; i++){
            N = Integer.valueOf(br.readLine());
            
            root = new int[N + 1];
            dis = new int[N + 1];
                        
            for(int j = 1; j <= N; j++) {
                root[j] = j;
                dis[j] = 0;
            }
        
            while(!(str = br.readLine()).equals("O")){
                String[] sArr = str.split(" ");
                
                if(sArr[0].equals("E")){
                    I = Integer.valueOf(sArr[1]);
                    find(I);
                    bw.write(dis[I] + "\n");
                }else{
                    I = Integer.valueOf(sArr[1]);
                    J = Integer.valueOf(sArr[2]);
 
                    union(I, J);
                }
            }
        }
 
        bw.flush();
     }
}