최소공통조상 (LCA, Lowest Common Ancestor)

최소공통조상은 트리에서 말 그대로 가장 가까운 공통 조상을 뜻한다. 

참고링크: https://www.crocus.co.kr/660

LCA(Lowest Common Ancestor) 알고리즘

 

코드로 구현시 핵심은 먼저 조상의 max_depth 지정이다. 이때 이 max_depth는 2^depth번째 조상을 구하기 위한 변수이기 때문에 조상을 구하는 최대 깊이는 log2(노드 최대 개수)를 올림한 값이 된다. 예를들어 노드 최대 개수가 3이라고 한다면 log2(3) 올림은 2가 된다. 2^2=4 즉 4의 범위로 3을 표현할 수 있게 된다.  다른 예로 8개라고 하면 log2(8)=3 , 2^3=8 이며 해당 범위로 8까지 표현 할 수 있게 된다. 

 

두 번째로 ac[here][i] = ac[ tmpac[here][i - 1] ][i - 1] 의 의미이다. 이는 현재 노드 here의 2^i 번째 조상은 here의 2^(i-1)번째 조상의 2^(i-1) 조상과 같다는 의미이다. here의 2^(i-1) 번째 조상의 2^(i-1) 번째 조상은 2^(i-1) + 2^(i-1)=2^i 즉 here의 2^i번째 조상 (결국 같은 말). 이를 통해 우리는 찾고자하는 공통조상을 log(n)의 시간복잡도로 탐색할 수 있다.

 

관련예제:

 

백준 11438 LCA2 : https://www.acmicpc.net/problem/11438

11438번: LCA 2

소스코드

 

 

 

백준 3176 도로네트워크: https://www.acmicpc.net/problem/3176

3176번: 도로 네트워크

기존 LCA 문제에서 ac[here][i] 를 구조체타입으로 변형하여 문제를 해결해야하는 문제이다. 

노드부터 다른 노드까지 연결하는 모든 도로 중에서 가장 길고 짧은 도로의 길이를 출력해야 한다. 핵심은 ac[here][i]를 초기화 시켜주는 과정에 있다.  앞서 구했던 과정에서는 ac[here][i] = ac[ tmpac[here][i - 1] ][i - 1] 점화식을 통해 해당 노드의 2^i 번째 노드가 무엇인지 구할 수 있다. max,min도 점화식을 통해 구할 수 있는데 이때 점화식을 구할때 의미만 잘 부여를 해주면 된다. "ac[here][i].MAX =max(ac[here][i-1],ac[ ac[here][i-1] ][i-1])" here의 2^i번째까지 max값은 here 서부터 2^(i-1) 까지의 max값과  here의 2^(i-1) ~ 2^i 까지의 max값 이 둘중 하나를 max로 취한다는 뜻이며 이때 i의 범위설정을 잘 해야 한다. 2^i <= depth[here]-1 (-1을 하는 이유는 루트의 depth를 1로 했기 때문)

즉 i가 i<= (int)floor(depth[here]-1) 라는 조건 안에 들어 올때 위의 점화식을 적용시키면 here의 2^i 번째까지의 max나 min의 값을 구할 수 있다.

 

마지막으로 main에서 최대 최소를 구하는 방법이다. lca 를 구할 때와 마찬가지로 b의 값을 끌어올리는 방식으로 하는데 이때 b의 값을 끌어올릴때마다 max나 min의 값도 마찬가지로 끌어 올려준 만큼 변경을 해야 한다. 그리고 a,b 두 노드의 depth를 맞추게 되면 두 노드를 동시에 올려주는데 이때 올려줄때마다 max,min 의 값도 변경한다. 그리고 최종적으로 이 두 max,min의 값은2^0 까지 고려를 해주지 않은 상태이므로 이를 고려하여 한 번 더 max min을 변경해줘야 하고 마지막에 maxa 와 maxb중 (최소 공통 조상 기준 왼쪽 max , 오른쪽 max) 중 max값을 선택해 출력해 주면 된다.

 

소스코드