[1. 문제 설명]
https://www.acmicpc.net/problem/1761
[2. 풀이 접근]
구해야 하는 노드 쌍의 개수가 1개라면, 단순한 접근으로 풀 수 있지만,
최대 1만개의 노드 쌍의 거리를 구해야 하므로, 단순한 접근으로는 시간 초과 발생이 매우 높다.
- 트리가 한쪽 방향으로 스큐되어 있다고 생각해보면,
- Leaf 에서 Root 까지 올라갈 때, 하나의 노드쌍에 대해서 O(H) 걸림
- 쿼리 개수는 총 M 개
- 단순한 접근 시 전체 시간복잡도는 O(HM)
=> H 는 최대 4만, M 은 최대 1만,
즉, LCA 를 구할 때, 좀 더 빠른 방법으로 구해야 한다.
Sparse table 을 전처리 과정에서 구한 뒤,
LCA 를 찾아가고, 그 과정에서 이동 거리를 구한다면,
쿼리 하나 당 거의 상수시간에 가까운 복잡도로 해결 할 수 있다.
[3. 코드]
'알고리즘 > Baekjoon' 카테고리의 다른 글
| 완전 탐색. [2309, 1182] (0) | 2022.12.30 |
|---|---|
| SCC. [2152] (0) | 2022.12.29 |
| 위상정렬. [1516] (0) | 2022.12.27 |
| 최소신장트리. [1647] (0) | 2022.12.26 |
| 최단경로. [2458] (0) | 2022.12.25 |
