백준 11437. LCA

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

11437번: LCA

 

공통 부모를 찾는 방법은 금방 생각해냈는데 이상한데서 삽질을 했다.

 

우선 공통 부모를 찾는 방법은 다음과 같다.

1. 모든 노드들의 깊이를 기록한다. (루트는 노드1로 주어진다)

2. 두 노드의 공통 부모를 찾을때, 두 노드의 깊이가 다르다면 맞춰준다. 

    -> 깊이가 더 깊은 노드를 깊이가 낮은 노드까지 부모로 올라가면 된다.

3. 깊이를 맞췄으므로 1 칸씩 부모로 올라가다가, 같은 노드를 만나면 그 노드가 가장 까까운 공통 조상이다. 

 

내가 삽질한건  두 노드가 주어지면, 부모로 거슬러 올라가야 하므로 누가 부모이고 누가 자식인지 판단해야 하는 부분인데, 생각해보면 부모는 한개 일 수 밖에 없으므로 그냥 깊이 기록하면서 이전 노드를 부모로 기록하면 된다.