백준 3780 (네트워크 연결)

문제

---

종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다.

어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다.

1. 클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다.
2. 클러스터 B를 제공하는 기업 J를 고른다. B는 A가 아닌 임의의 클러스터이며, J는 센터가 아닐 수 있다.
3. I와 J를 통신 라인으로 연결한다. 이때 기업 I와 J를 잇는 라인의 길이는 |I – J|(mod 1000)이다.
4. 위 방식을 통해 클러스터 A와 B는 새로운 클러스터로 합쳐지며, 이 클러스터는 B의 센터에 의해 제공된다.

이러한 병합 과정을 거치던 중에, 각 기업에서 현재 센터까지 연결되는 라인의 길이가 총 얼마나 되는지에 관한 문의가 들어왔다. 서현이를 위해 병합하는 과정과 그 과정에서 통신센터와 각 기업을 잇는 라인의 길이를 구하는 프로그램을 작성해보자.

 

 

 

풀이

---

바로 연결된 기업과의 거리를 통해 더하는 방식을 사용했더니 시간 초과가 나왔다.

 

거리를 계속 최신화 하는 배열을 만들어서 연결된 센터와 센터와의 거리를 계속 최신화 해주어야한다.

 

Union 함수는 아래와 같다.

static void union(int i, int j) {
	
	len[i] = Math.abs(i - j) % 1000;
	
	parent[i] = j;
}

 

아래와 같이 센터와의 거리로 값을 초기화 시켜준다.

 

Find 함수는 아래와 같다.

static int find(int i) {
	
	if(parent[i] == i) {
		return i;
	}
	else {
		int tmp = find(parent[i]);
		len[i] += len[parent[i]];
		parent[i] = tmp;			
		
		return parent[i];
	}
		
}

 

해당 값의 부모를 찾을 때까지 재귀를 하는 방식은 같지만,

 

자기자신이 부모가 아닌경우 센터와의 거리를 최신화 하여 준다.

 

 

<전체코드>

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	static int[] parent;
	static int[] len;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(bufferedReader.readLine());
		
		for(int i = 0 ; i < t ; i++) {
			int n = Integer.parseInt(bufferedReader.readLine());
			
			parent = new int[n + 1];
			len = new int[n + 1];
			for(int j = 1 ; j <= n ; j++) {
				parent[j] = j;
			}
			while(true) {
				String[] doing = bufferedReader.readLine().split("\\s");
			
				if(doing[0].equals("O")) {
					break;
				}
				else if(doing[0].equals("E")) {
					find(Integer.parseInt(doing[1]));
					
					sb.append(len[Integer.parseInt(doing[1])] + "\n");
				}
				else if(doing[0].equals("I")){
					union(Integer.parseInt(doing[1]), Integer.parseInt(doing[2]));
				}
			}
			
		}
		
		System.out.println(sb);
	}

	static int find(int i) {
		
		if(parent[i] == i) {
			return i;
		}
		else {
			int tmp = find(parent[i]);
			len[i] += len[parent[i]];
			parent[i] = tmp;			
			
			return parent[i];
		}
		
	}
	
	static void union(int i, int j) {
		
		len[i] = Math.abs(i - j) % 1000;
		
		parent[i] = j;
	}
}