SWEA 1248: 공통조상

노드 v1와 v2의 공통 조상 노드를 찾는 문제이다.

전체 트리에서 루트가 되는 정점은 항상 1번으로 표기된다. -> 이 조건 때문에 더 쉬움

 

방법 1 - 부모 노드에 대한 링크가 있는 경우 => 최대 높이가 d일 때, 공통 조상을 찾는데까지 시간 복잡도 O(d)

1. v1, v2를 루트 노드에서 거리를 구한다.

2. v1, v2를 같은 높이가 될 때까지 한 노드의 높이를 올려준다.

3. v1, v2의 높이를 하나씩 올리면서 겹치는 경우를 찾는다.

class Solution {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int test = in.nextInt();
		for (int t = 1; t <= test; t++) {
			int n = in.nextInt();
			int e = in.nextInt();
			int v1 = in.nextInt();
			int v2 = in.nextInt();

			LinkedList<Integer> childs[] = new LinkedList[n + 1];
			for (int i = 1; i <= n; i++) {
				childs[i] = new LinkedList<Integer>();
			}
			int[] parent = new int[n + 1];

			for (int i = 0; i < e; i++) {
				int p = in.nextInt();
				int c = in.nextInt();

				childs[p].add(c);
				parent[c] = p;
			}

			int height1 = heightFromRootNode(v1, childs);
			int height2 = heightFromRootNode(v2, childs);

			int commonNode = findCommonParent(v1, v2, height1, height2, parent);
			int subNodes = calculateSubNodes(commonNode, childs);
			System.out.println("#" + t + " " + commonNode + " " + subNodes);
		}
	}

	private static int calculateSubNodes(int name, LinkedList<Integer>[] childs) {
		int answer = 0;

		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(name);

		while (!queue.isEmpty()) {
			int now = queue.poll();
			answer++;

			queue.addAll(childs[now]);
		}

		return answer;
	}

	private static int findCommonParent(int v1, int v2, int height1, int height2, int parent[]) {
		// 무조건 height1 <= height2라고 생각 -> v2를 위로 땡긴다.
		if (height1 > height2) {
			return findCommonParent(v2, v1, height2, height1, parent);
		}

		while (height1 != height2) {
			v2 = parent[v2];
			height2--;
		}

		while (v1 != v2) {
			v1 = parent[v1];
			v2 = parent[v2];
		}

		return v1;
	}

	private static int heightFromRootNode(int name, LinkedList<Integer>[] childs) {
		int height = 0;

		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(1);

		while (!queue.isEmpty()) {
			int size = queue.size();
			height++;
			for (int i = 0; i < size; i++) {
				int parent = queue.poll();

				if (parent == name) {
					return height;
				}

				queue.addAll(childs[parent]);
			}
		}

		return height;
	}
}

 

방법 2 -