boj 11437: LCA

LCA: Lowest common Ancestor

두 노드의 가장 가까운 공통 조상을 찾는 문제이다.

 

LCA를 찾기 위해서는 두 노드의 level과 부모를 알아야한다.

 

따라서

• 두 노드의 레벨이 다르면, 레벨이 같을 때까지 레벨이 큰 것을 한 칸씩 위로 올린다.
• 두 노드의 레벨이 같아지면, 같은 노드가 될 때까지 한 칸씩 위로 올린다.

인접 행렬을 사용하면 메모리 초과가 생기고,

Queue에 pair을 저장하면 나중에 bfs를 돌 때 시간 초과가 생기므로

LinkedList의 배열에  pair을 저장하고 바로 꺼내 쓸 수 있도록 한다.

 

이 문제의 주의할 점은 입력 시 어떤 노드가 parent이고 어떤 노드가 child인지 알 수 없으므로

bfs을 돌 때 parent와 child를 정의할 수 있다.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		int[] depth = new int[n + 1];
		int[] parentNode = new int[n + 1];
		boolean[] isVisited = new boolean[n + 1];
		LinkedList<Integer> pair[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			pair[i] = new LinkedList<Integer>();
		}

		for (int i = 1; i < n; i++) {
			int node1 = in.nextInt();
			int node2 = in.nextInt();
			pair[node1].add(node2);
			pair[node2].add(node1);
		}

		depth = calculateNodeDepth(pair, parentNode, n);

		int test = in.nextInt();
		int ans = 1;
		for (int t = 0; t < test; t++) {

			int node1 = in.nextInt();
			int node2 = in.nextInt();

			int depth1 = depth[node1];
			int depth2 = depth[node2];

			if (depth1 < depth2) {
				ans = calculateLCA(parentNode, depth, node2, node1);
			} else{
            	ans = calculateLCA(parentNode, depth, node1, node2);
            }
			System.out.println(ans);
		}
	}

	public static int calculateLCA(int parent[], int depth[], int node1, int node2) {

		int depth1 = depth[node1];
		int depth2 = depth[node2];
		int ans = 1;

		while (depth1 > depth2) {
			node1 = parent[node1];
			depth1 = depth[node1];
		}

		while (node1 != node2) {
			node1 = parent[node1];
			node2 = parent[node2];
		}

		ans = node1;
		return ans;
	}

	public static int[] calculateNodeDepth(LinkedList<Integer> pair[], int parent[], int n) {
		Queue<Integer> queue = new LinkedList<Integer>();
		int depth[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];

		queue.add(1);
		depth[1] = 0;
		isVisited[1] = true;

		while (!queue.isEmpty()) {

			int node = queue.poll();

			for (int i : pair[node]) {
				if (!isVisited[i]) {
					queue.add(i);
					depth[i] = depth[node] + 1;
					parent[i] = node;
					isVisited[i] = true;
				}
			}
		}
		return depth;
	}
}