[백준 03584] 가장 가까운 공통 조상 [Java]

문제

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

---

풀이

주어지는 트리에 대해 두 정점의 공통 조상을 찾는 문제다.

이미 부모-자식에 대한 정보가 주어지므로, 입력과 동시에 parent를 바로 구성할 수 있다. 

공통 조상을 구해야하는 두 정점 중 한 정점으로부터 루트노드까지 방문해주고,

다른 정점도 동일하게 방문하지 않은 부모 노드를 따라 방문하면 된다.

이미 방문한 적 있는 부모노드는 공통 조상 노드이므로 탐색을 중단하고 반환해주면 된다.

---

소스코드

보기