[백준][트리] 11437 LCA

LCA 문제는 우선 트리형태를 구성해서

BFS를 이용하여 현재 노드의 부모노드, 깊이를 구한다. 

그다음 깊이를 동일하게 설정하고, 

한단계씩 올라오면서 부모가 같아지면 그때 

부모를 출력하면 해결할 수 있다. 

	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Scanner;
	/**
	* 백준 11437
	* LCA(Longest Common Ancetor)
	*
	* @author whitebeard-k
	*
	*/
	public class Problem11437 {
	static int N;
	static int M;
	static int[] parent; // 부모의 노드 번호
	static int[] depth; // 깊이
	static LinkedList<Integer>[] list;
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	list = new LinkedList[N + 1];
	for (int i = 1; i <= N; i++) {
	list[i] = new LinkedList<>();
	}
	// 간선의 정보 입력
	for (int i = 0; i < N - 1; i++) {
	int x = sc.nextInt();
	int y = sc.nextInt();
	list[x].add(y);
	list[y].add(x);
	}
	// 루트는 1번
	int START = 1;
	parent = new int[N + 1];
	depth = new int[N + 1];
	Queue<Integer> queue = new LinkedList<>();
	queue.add(START);
	parent[START] = START;
	depth[START] = START;
	while (!queue.isEmpty()) {
	int from = queue.poll();
	for (int to : list[from]) {
	if (parent[to] == 0) {
	// 아직 부모의 정보가 없는 노드이면 큐에 추가하고 부모의 정보와 깊이 정보를 입력
	queue.add(to);
	parent[to] = from;
	depth[to] = depth[from] + 1;
	}
	}
	}
	M = sc.nextInt();
	while (M-- > 0) {
	int x = sc.nextInt();
	int y = sc.nextInt();
	// 깊이가 더 깊은 쪽을 y 로 설정한다.
	if (depth[x] > depth[y]) {
	int temp = x;
	x = y;
	y = temp;
	}
	// 같은 높이가 되도록 끌어 올린다.
	while (depth[x] != depth[y]) {
	y = parent[y];
	}
	if (x == y) {
	System.out.println(x);
	} else {
	// 같은 부모가 될때까지 올라간다.
	while (parent[x] != parent[y]) {
	x = parent[x];
	y = parent[y];
	}
	System.out.println(parent[x]);
	}
	}
	sc.close();
	}
	}

view raw Problem11437_LCA.java hosted with ❤ by GitHub

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