[ 백준 / 3780] 네트워크 연결 ( JAVA )

www.acmicpc.net/problem/9938

9938번: 방 청소

 

 

 Union-Find를 통해서 해결이 가능하다. 처음에 문제를 이해하는데 오래 걸렸다. 이 문제의 특징은 단순히 union으로 관계를 설정하고, find를 통해서 관계를 발견하는 것이 끝이 아니다. 거리가 존재하기 때문에, 이를 계속 업데이트 해주어야 한다. 따라서 parent 배열 이외에도 dis 배열을 하나 만들어서 계속 거리 값을 최신화했다.

 

 처음에 단순히 부모의 값만 저장하여 계산하였더니 시간초과가 나왔다. 따라서, find를 통해서 새로운 관계를 만들 때마다 dis를 최신화해야 했다. 결국에는 parent에 root parent 값이 들어간다. 재귀를 통해서 이 과정이 진행되며, 처음에는 이해하는 것이 다소 어려웠다. 즉, parent[x] ==x 는 root를 의미하므로 그대로 반환하며, 그렇지 않은 경우 dis는 계속 현재 x의 길이에 부모의 길이를 더하도록 하면 된다. 

 

import java.util.*;
import java.io.*;

public class Main {

	static int[] parent;
	static int[] dis;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			int N = Integer.parseInt(br.readLine());
			parent = new int[N + 1];
			dis = new int[N+1];
			
			for (int i = 1; i <= N; i++) {
				parent[i] = i;
			}

			String line="";
			
			while (!(line = br.readLine()).equals("O")) {
				String[] input = line.split(" ");
				
				if (input[0].equals("E")) {
					int to = Integer.parseInt(input[1]);
					find(to);
					System.out.println(dis[to]);
				} else {
					int front = Integer.parseInt(input[1]);
					int back = Integer.parseInt(input[2]);
					parent[front] = back;
					dis[front] = Math.abs(front-back)%1000;
				}
			}
		}
	}
	
	public static int find(int x) {
		if(parent[x]==x) return x;
		
		int tmp = find(parent[x]);
		dis[x] += dis[parent[x]];
		parent[x] = tmp;
		
		return parent[x];
	}
}