트리에서 두 노드의 가장 깊이가 깊은 공통 조상을 찾는 문제입니다.
1. 각 각의 두 노드에 대해 root 부터 자신의 부모까지를 stack으로 저장합니다.
(계산의 편의를 위해 stack으로 집어넣어 root가 가장 맨 위에 들어가게 했습니다.)
2. 두 노드의 부모 stack을 앞에서부터 하나씩 빼면서 서로 부모가 달라질 때 까지 값을 뽑습니다.
(당연히 맨 처음에 뽑히는 건 root입니다.)
3. 스택에서 서로 부모가 달리지기 직전에 뽑힌 동일한 부모가 가장 가까운 공통 조상입니다.
코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ3584.cc
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ]1167번: 트리의 지름 (0) | 2021.03.10 |
---|---|
[BOJ]3197번: 백조의 호수 (0) | 2021.03.08 |
[BOJ]1516번: 게임 개발 (0) | 2021.03.05 |
[BOJ]1766번: 문제집 (0) | 2021.03.04 |
[BOJ]2056번: 작업 (0) | 2021.03.04 |