https://www.acmicpc.net/problem/11438
최소 공통 조상 (Lowest Common Ancestor)를 찾는 알고리즘이다.
1. dfs로 트리를 만든다. 이때 노드별 깊이 정보와(root 깊이 = 0) 가장 첫번째 부모 정보를 잡아준다.
2. 노드 A의 2^k번째 부모 노드는, A의 2^k-1번째 부모 노드의 2^k-1번째 부모 노드와 같다는 것을 이용해서 바텀업 dp로 부모 배열을 채운다.
3. 공통 조상을 찾을 a, b가 있다면, 우선 깊이가 깊은 곳과 낮은 곳을 확실히 구분해준다. 그리고 둘의 높이를 맞춰준다.
n개의 노드가 있다고 했을 때, 2의 거듭제곱으로 타고 올라갈 수 있는 최대 높이가 MAXK =(int)floor(log2(n)); 이다.
두 노드의 높이 차이가, 위에서부터 보고 내려온 2의k승보다 크거나 같아지는 순간마다 깊은 노드를 해당하는 2의 k번째 부모로 갱신한다.
결국 높이가 같아지게 되고, 이때 두 노드의 값이 같다면 반환해주면 된다.
그렇지 않다면
4. 위와 비슷한 방식으로, 2의최대 거듭제곱부터 아래로 내려오면서 부모의 노드가 같은지 확인한다. 다를때마다 두 노드를 다른 순간의 2의 k승번째 노드로 갱신해준다. 결국 둘이 같아지게 된다
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include<iostream> #include<vector> #include<cmath> #include<algorithm> using namespace std; int n, m, dep[100002], MAXK, parent[100002][20]; bool vis[100002]; vector<int> e[100002]; void makeTree(int here, int depth) { //트리 만들면서 첫번째 부모와 깊이를 채움 //if (vis[here]) return; //continue문 주석 풀고 여길 주석해도 똑같음 vis[here] = true; dep[here] = depth; for (int i = 0; i < e[here].size(); i++) { int next = e[here][i]; if (vis[next]) continue; parent[next][0] = here; //첫번째 부모 저장 makeTree(next, depth + 1); } } void fillParent() { //바텀업으로 부모 배열 채워줌 for (int k = 1; k <= MAXK; k++) for (int i = 1; i <= n; i++) parent[i][k] = parent[parent[i][k - 1]][k - 1]; } int lca(int swall, int deep) { if (dep[deep] < dep[swall]) swap(deep, swall); for (int k = MAXK; k >= 0; k--) { //높이를 동일하게 맞춰줌 int dif = dep[deep] - dep[swall]; if (dif >= (1 << k)) deep = parent[deep][k]; } if (deep == swall) return deep; //printf("deep swall 중간 %d %d\n", deep, swall); for (int k = MAXK; k >= 0; k--) { if (parent[deep][k] != parent[swall][k]) { deep = parent[deep][k]; swall = parent[swall][k]; } } return parent[deep][0]; } int main(void) { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 0; i < n-1; i++) { //node가 n개고 간선은 n-1개 int src, dst; cin >> src >> dst; e[src].push_back(dst); e[dst].push_back(src); } makeTree(1, 0); //root = 1, root depth = 0 MAXK =(int)floor(log2(n)); //포함 -> 최대높이***************** fillParent(); cin >> m; while (m--) { int a, b; cin >> a >> b; cout << lca(a, b) << '\n'; } return 0; } | cs |
'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글
| 백준 1753 최단경로 C++ (0) | 2019.08.15 |
|---|---|
| 백준 1916 최소비용 구하기 C++ (0) | 2019.08.15 |
| 백준 1197 최소 스패닝 트리 C++ (0) | 2019.08.15 |
| 백준 1516 게임 개발 C++ (0) | 2019.08.15 |
| 백준 2056 작업 C++ (0) | 2019.08.15 |