[Algorithm] 👨‍👩‍👧백준 3584 가장 가까운 공통 조상

0. 문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

* 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.
예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력
첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력
각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

1. 아이디어

💡 주어진 숫자의 depth를 구함
💡 depth가 다르다면, 큰 숫자가 부모노드로 올라가 depth가 같아지게 함
💡 depth가 서로 같다면, 같은 숫자가 나올때까지 부모노드로 올라감

2. 핵심 풀이

1) 주어진 숫자의 depth를 구함

static int depth(int node) {
	int dep = 0;
	int cur = node;
		
	while(cur != 0) {
		dep++;
		cur = parent[cur];
	}
		
	return dep-1;
}

2) depth가 다르다면, 큰 숫자가 부모노드로 올라가 depth가 같아지게 함

if(aDepth > bDepth) {
	while(aDepth != bDepth) {
		aDepth--;
		a = parent[a];
	}
} else if(bDepth > aDepth) {
	while(bDepth != aDepth) {
		bDepth--;
		b = parent[b];
	}
}

3) depth가 서로 같다면, 같은 숫자가 나올때까지 부모노드로 올라감

while(a!=b) {
	a = parent[a];
	b = parent[b];
}

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Graph_4 {
	static int[] parent;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		while(T-->0) {
			int N = Integer.parseInt(br.readLine());
			
			parent = new int[N+1];
			String[] s;
			
			for(int i=0; i<N-1; i++) {
				s = br.readLine().split(" ");
				parent[Integer.parseInt(s[1])] = Integer.parseInt(s[0]);
			}
			
			s = br.readLine().split(" ");
			int a = Integer.parseInt(s[0]);
			int b = Integer.parseInt(s[1]);
			
			int aDepth = depth(a);
			int bDepth = depth(b);
			
			System.out.println(find(a,b,aDepth,bDepth));
			
		}
		
	}
	
	static int depth(int node) {
		int dep = 0;
		int cur = node;
		
		while(cur != 0) {
			dep++;
			cur = parent[cur];
		}
		
		return dep-1;
	}
	
	static int find(int a, int b, int aDepth, int bDepth) {
		if(aDepth > bDepth) {
			while(aDepth != bDepth) {
				aDepth--;
				a = parent[a];
			}
		} else if(bDepth > aDepth) {
			while(bDepth != aDepth) {
				bDepth--;
				b = parent[b];
			}
		}
		
		while(a!=b) {
			a = parent[a];
			b = parent[b];
		}
		
		return a;
	}
}

4. 결과

성공✨