[SWEA] 1248. 공통조상

[1248. [S/W 문제해결 응용] 3일차 - 공통조상]

문제

---

공통 조상을 찾은 후에 그 서브트리의 크기를 구하는 문제이다. LCA 를 사용하였다. </br>LCA 알고리즘.

실수

---

트리가 존재하는 것이 아니라 간선을 모두 받아와서 트리를 생성해야한다. 좀 더 효율적인 방법이 당연히 존재하겠지만 문제 통과 조건이 20초 이상이기에 단순하게 구현했다.

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	static StringBuilder result = new StringBuilder();

	static int[] depth = new int[10001];
	static int[][] parent = new int[10001][14];
	static int[][] child = new int[10001][101];

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		///////////////////////////
		int V, E, v1, v2, cnt, p, c;
		///////////////////////////
		for (int test_case = 1; test_case <= T; test_case++) {
			result.append("#" + test_case + " ");
			/////////////////////////////
			StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

			V = Integer.parseInt(stringTokenizer.nextToken());
			E = Integer.parseInt(stringTokenizer.nextToken());
			v1 = Integer.parseInt(stringTokenizer.nextToken());
			v2 = Integer.parseInt(stringTokenizer.nextToken());

			for (int i = 0; i < 10001; i++) {
				depth[i] = 0;
				for (int j = 0; j < 14; j++) {
					parent[i][j] = 0;
				}
				for (int j = 1; j <= child[i][0]; j++) {
					child[i][j]=0;
				}
				child[i][0] = 0;
			}

			stringTokenizer = new StringTokenizer(br.readLine());

			for (int i = 0; i < E; i++) {
				p = Integer.parseInt(stringTokenizer.nextToken());
				c = Integer.parseInt(stringTokenizer.nextToken());

				parent[c][0] = p;
				child[p][0]++;
				child[p][child[p][0]] = c;
			}

			Queue<Integer> depthQueue = new LinkedList<>();
			depthQueue.add(1);
			while (!depthQueue.isEmpty()) {
				int cur = depthQueue.poll();
				for (int i = 1; i <= child[cur][0]; i++) {
					depthQueue.add(child[cur][i]);
				}
				depth[cur] = depth[parent[cur][0]] + 1;
			}

			int K = 0;
			int k = 1;
			while (k <= V) {
				k = k << 1;
				K++;
			}
			makeParents(K, V);
			int root = lca(v1, v2, K);

			cnt = 0;

			Queue<Integer> subTreeQueue = new LinkedList<>();
			subTreeQueue.add(root);
			while (!subTreeQueue.isEmpty()) {
				int cur = subTreeQueue.poll();
				for (int i = 1; i <= child[cur][0]; i++) {
					subTreeQueue.add(child[cur][i]);
				}
				cnt++;
			}

			result.append(root + " " + cnt + "\n");
			System.out.print(result);
			result.setLength(0);
		}
	}

	static int lca(int a, int b, int K) {
		if (depth[a] < depth[b]) { // 깊이가 낮은 쪽을 기준으로 맞춘다.
			int temp = a;
			a = b;
			b = temp;
		}

		for (int i = K - 1; i >= 0; i--) {
			if (Math.pow(2, i) <= depth[a] - depth[b]) {
				a = parent[a][i];
			}
		}

		if (a == b)
			return a;
		for (int i = K - 1; i >= 0; i--) {
			if (parent[a][i] != parent[b][i]) {
				a = parent[a][i];
				b = parent[b][i];
			}
		}
		return parent[a][0];
	}

	static void makeParents(int K, int N) {
		for (int i = 1; i < K; i++) {
			for (int j = 1; j <= N; j++) {
				parent[j][i] = parent[parent[j][i - 1]][i - 1];
			}
		}
	}

}