백준 11437번 LCA

BOJ 11437번 LCA https://www.acmicpc.net/problem/11437

 

풀이:

다른 사람들이 왜 이렇게 풀어야만 했는지 이해를 못해서.... 한참 헤맸다

문제에 주어지지 않는 게 있는데

*부모-자식 관계의 정의*가 주어지지 않는다.

1. 주어진 정점들을 다 연결했을 때 1과 가까운 노드가 부모가 된다.

최상위가 1번이라서 작은수가 부모가 된다고 착각하면 방황하게 된다ㅠㅠ

정점을 하나씩 탐색 돌리면 시간 초과가 뜨고, 문제는 항상 한 쌍으로 주어지기 때문에

2. 반복문(for/while) 하나에서 두 정점을 동시에 탐색해야 한다.

두 정점을 동시에 탐색하려면 각 정점의 단계(Level)을 알아야한다.

정점별로 탐색을 돌리면 시간초과가 뜨기 때문에

3. 각 정점별 단계를 미리 단계를 알아놔야한다. 

두 정점을 잇는 간선정보가 차례대로 주어지지 않기 때문에

4. 간선정보를 전부 받아 탐색을 통해 단계를 확인해야한다.

5. 탐색 전에는 부모-자식 관계를 알 수 없기 때문에 일단 양방향 노드로 구현한다.

 

 

 

단계가 서로 다르기 때문에 하위 단계 정점을 먼저 위로 끌어올려 맞춰야한다

부모-자식 관계는 간선 정보상 1에 가까운 정점이 부모가 된다