[백준 11437] LCA [Java]

문제

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

---

풀이

DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.

이를 위해서 양방향 그래프를 구성해야 합니다.

문제에서 트리의 루트는 1번이라 언급되어 있으니, 1번 정점부터

DFS를 통해 모든 노드의 부모 노드와, 깊이를 구해주면 된다.

이제 LCA를 구해야 하는 두 노드 u, v에 대해 깊이가 다르다면 부모 노드로 올라가며 깊이를 맞춰주고,

깊이가 동일한 두 노드의 부모노드가 같을 때까지, 즉 LCA를 찾아주면 된다.

---

소스코드

보기