백준 #10838 #Java

https://www.acmicpc.net/problem/10838

이 문제는 최소공통조상을 찾아야지 최단 경로를 알아낼 수 있다.
저는 처음에 각 노드별로 깊이를 저장하고 깊이를 줄여가면서 최소공통조상을 찾았다. 그러다보니 노드를 이동시킬 때 옮기는 서브트리 전부 순회하면서 깊이를 변화시켜줘야 했고 시간초과가 나오게 됐다.

위 방법 말고 두 노드를 부모노드로 이동시키면서 방문여부를 체크하고 최초로 두번 방문하는 노드를 최소공통조상으로 두는 방법으로 해야 시간안에 해결할 수 있다.

트리가 변하는 상황에서는 두번째 방법이 빠른 것 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	static int n, k;
	static int[] parentOf;
	static int[] colorOf;
	static boolean[] visit;
	public static void main(String[] args) throws Exception{
			
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		parentOf = new int[n];
		colorOf = new int[n];
		visit = new boolean[n];

		for (int i=1; i<n; i++) {
			parentOf[i] = 0;
		}

		StringBuilder sb = new StringBuilder();

		for (int i=0; i<k; i++) {

			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			switch (r) {

				case 1: // paint
					int c = Integer.parseInt(st.nextToken());
					paint(a, b, c);
					break;

				case 2: // move
					parentOf[a] = b;
					break;

				case 3: // count
					sb.append(count(a, b)).append('\n');
					break;
			}
		}
		System.out.print(sb.toString());
	}

	static int findAncestor(int a, int b) {
		int cnt = 0;
		visit = new boolean[n];
		visit[a] = true;
		while (cnt < 1000) {
			a = parentOf[a];
			visit[a] = true;
			cnt ++;
		}
		cnt = 0;
		while (cnt < 1000) {
			if (visit[b]) return b;
			b = parentOf[b];
		}
		return 0;
	}

	static void paint(int a, int b, int c) {
		
		int ancestor = findAncestor(a, b);
		while (a != ancestor) {
			colorOf[a] = c;
			a = parentOf[a];
 		}
		while (b != ancestor) {
			colorOf[b] = c;
			b = parentOf[b];
		}
	}
	
	static int count(int a, int b) {

		HashSet<Integer> set = new HashSet<>();

		int ancestor = findAncestor(a, b);
		while (a != ancestor) {
			set.add(colorOf[a]);
			a = parentOf[a];
 		}
		while (b != ancestor) {
			set.add(colorOf[b]);
			b = parentOf[b];
		}
		return set.size();
	}

}