[BOJ]3584번: 가장 가까운 공통 조상

www.acmicpc.net/problem/3584

---

트리에서 두 노드의 가장 깊이가 깊은 공통 조상을 찾는 문제입니다.

 

1. 각 각의 두 노드에 대해 root 부터 자신의 부모까지를 stack으로 저장합니다.

(계산의 편의를 위해 stack으로 집어넣어 root가 가장 맨 위에 들어가게 했습니다.)

 

2. 두 노드의 부모 stack을 앞에서부터 하나씩 빼면서 서로 부모가 달라질 때 까지 값을 뽑습니다.

(당연히 맨 처음에 뽑히는 건 root입니다.)

 

3. 스택에서 서로 부모가 달리지기 직전에 뽑힌 동일한 부모가 가장 가까운 공통 조상입니다.

---

코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ3584.cc