최소공통조상 (LCA, Lowest Common Ancestor)
최소공통조상은 트리에서 말 그대로 가장 가까운 공통 조상을 뜻한다.
참고링크: https://www.crocus.co.kr/660
LCA(Lowest Common Ancestor) 알고리즘
LCA(Lowest Common Ancestor) 알고리즘이란? LCA 알고리즘이란 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고, 두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다. 예를들어 다음..
www.crocus.co.kr
코드로 구현시 핵심은 먼저 조상의 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
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.
www.acmicpc.net
소스코드
백준 3176 도로네트워크: https://www.acmicpc.net/problem/3176
3176번: 도로 네트워크
문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B
www.acmicpc.net
기존 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값을 선택해 출력해 주면 된다.
소스코드