[BOJ] 3584

less than 1 minute read

가장 가까운 공통 조상

3584번 https://www.acmicpc.net/problem/3584

최소 공통 조상(LCA: Lowest Common Ancestor)을 구하는 문제입니다.
주어진 두 노드의 depth가 같다면 두 노드가 같아질 때까지 각각을 각각의 부모로 갱신해줍니다.
주어진 두 노드의 depth가 다르다면 더 깊이 있는 노드를 더 얕게 있는 노드의 depth에 있는 부모로 갱신해줍니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/3584.cpp

Categories:

Updated:

Leave a comment