알고스팟 문제 링크: https://algospot.com/judge/problem/read/FAMILYTREE
algospot.com :: FAMILYTREE
족보 탐험 문제 정보 문제 촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되
algospot.com
0번 노드는 루트이고 1번부터 n-1번까지 각 노드의 parent의 번호가 주어진다.
정수로 노드의 번호 a, b가 주어질때 a와 b사이의 촌수(거리)를 구하는 문제이다.
문제에 제시된 트리를 전위탐색하면서 노드를 방문할때마다 trip이라는 vector안에 넣는다. 이때 depth와 현재 노드의 최초 방문 순서를 저장한다.
trip을 활용하여 RMQ를 생성하고 a, b의 공통조상을 찾는데 활용한다.
a, b의 거리는 ( a의 depth - 공통조상의 depth ) + ( b의 depth - 공통조상의 depth) 이다.
코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/FAMILYTREE.cpp
GitHub - sbl133/JongmanBook
Contribute to sbl133/JongmanBook development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2
'Algorithm > algospot' 카테고리의 다른 글
| algospot 에디터 전쟁 (문제 ID: EDITORWARS) c++ (0) | 2021.10.18 |
|---|---|
| algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++ (0) | 2021.10.15 |
| algospot 등산로 (문제 ID: MORDOR) c++ (0) | 2021.10.14 |
| algospot 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN)c++ (0) | 2021.10.11 |
| algospot 삽입 정렬 뒤집기 (문제 ID: INSERTION) c++ (0) | 2021.10.09 |