문제
https://www.acmicpc.net/problem/11438
풀이
기존에 선형 탐색으로 O(N)만에 LCA를 구하는 방법으로는 이 문제를 해결할 수 없다.
2025.01.15 - [PS/Baekjoon Online Judge] - [백준 11437] LCA [Java]
[백준 11437] LCA [Java]
문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1
kyr-db.tistory.com
각 쿼리에 대해 O(logN)안에 LCA를 찾을 수 있는 방법에 대해 알아보자.
깊이가 다른 두 노드의 깊이를 맞추고 LCA를 탐색하는 과정에서 부모 노드를 하나씩 탐색하는게 아닌, 2의 제곱수로 탐색하는 방법이다.
자세한 방법은 아래 글을 참고하자.
2025.01.25 - [Algorithm] - LCA, (Lowest Common Ancestor, 최소 공통 조상)
LCA, (Lowest Common Ancestor, 최소 공통 조상)
트리에서 두 노드 u, v의 가장 가까운 공통 조상을 찾는 알고리즘💡공통 조상이란?두 노드가 공통으로 공유하는 조상 노드의 집합= 루트 노트에서 두 노드로 가는 경로가 만나는 노드의 집합 트
kyr-db.tistory.com
각 노드에 대해 조상 노드 logN개를 저장할 배열 parent를 2차원 배열로 확장해주자
dfs를 하며 parent를 전처리해주자.
LCA 탐색 과정에서는 기존의 로직을 새로 변형된 parent에 맞춰서 변경해주면 된다.
소스코드
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 03584] 가장 가까운 공통 조상 [Java] (1) | 2025.01.25 |
|---|---|
| [백준 01006] 습격자 초라기 [Java] (0) | 2025.01.19 |
| [백준 03653] 영화 수집 [Java] (0) | 2025.01.17 |
| [백준 02533] 사회망 서비스(SNS) [Java] (0) | 2025.01.17 |
| [백준 11966] 2의 제곱인가? [Java] (0) | 2025.01.17 |