LCA

[JAVA]11437 LCA 공통 부모 노드 찾기(골드 3)

📚 문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 🔍 아이디어 공통 조상을 찾는 문제입니다. 각 노드의 깊이를 먼저 BFS, DFS를 이용하여 계산합니다. (이때 부모 노드도 함께 지정해줍니다, parents 배열) 이후에 a,b 노드의 공통 조상을 찾는 경우 a의 깊이, b의 깊이를 비교하여 두 노드의 깊이가 동일할 때까지 부모로 이동하며 올라옵니다 두 노드의 깊이가 같아졌으면 두 노드를 함께 부모로 노드로 올리는것을 반복합니다...