[BOJ] lca2

[문제]

https://www.acmicpc.net/problem/11438

11438번: LCA 2

[풀이]

11438

맞았습니다!!

16192

104

C++14 / 수정

2028

45초 전

 

1) 최소 공통 조상에 대한 개념은 crocus 님의 블로그 글을 참조함 (https://www.crocus.co.kr/660)

 

2) 최소 공통 조상을 구현할 때 가장 중요하게 생각해야 할 부분은 depth가 다르면 먼저 올려주고 비교 해야 한다는 것이다. 

depth가 같다 ? 공통 조상이다 

 

3) bfs로 먼저 트리를 구현한 후에 setParent라는 함수에서 dp를 사용하여 parent들을 넣어준다. 

parent[0] => 내 부모노드 번호를 저장한다. 

parent[1] => 내 부모의 부모를 저장한다.(할아버지)

parent[2] =>  할아버지의 할아버지를 저장한다. 

.. 2승식 거슬러 올라가면서 조상들의 노드를 저장한다. 

 

4) parent[][]는 이차원 배열로 원소에 따라서 2승 씩 올라가면서 조상들을 저장한다.

 

5) lca() 에서는 최소 공통 조상을 알고 싶은 원소들을 파라미터로 받아 서로 depth를 비교한다. 

(나는 항상 a가 더 낮은 깊이를 가지고 있다고 가정했다.)

 

6) depth를 비교하면서 b를 끌어올려준다. (더 높은 깊이에 있는 원소)

-> a==b라면 a가 b의 조상이다. 

 

7) 높이를 맞춰줬는데도 다르다면 이제 parent를 사용해서 더 위로 올라가면서 비교한다. 

 

---

#include <iostream>
#include <vector>
#include <queue>
 
#define MAX_N 100001
using namespace std;
 
//lca2 (최저 공통 조상 찾기 )
vector<int> edges[MAX_N];
bool visited[MAX_N];
int parent[MAX_N][21], depth[MAX_N]; //2 ^20 승 (노드의 개수가 최대 100000이기 때문에 )
 
void bfs() {
    queue<int> q;
 
    q.push(1); //1은 루트 노드라고 명시되어있음 
    visited[1] = true;
    depth[1] = 1; //깊이를 알기 위해 사용한 배열
    //조상을 찾을 때 깊이가 다르면 더 낮은 깊이로 맞춰줘야 한다. 
 
    while(!q.empty()) {
        int now = q.front(); q.pop();
 
        for (auto i : edges[now]) {
            if (!visited[i]) {
                visited[i] = 1;
                depth[i] = depth[now] + 1;
                q.push(i);
                parent[i][0] = now; //조상을 연결한다. 
            }
        }
    }
} //bfs
 
void setParent(int n) {
    for (int i = 1; i < 21; i++) {
        for (int j = 1; j <= n; j++ ) {
            parent[j][i] = parent[parent[j][i-1]][i-1];
        }
    }
}
 
int lca(int a, int b) {
    //a가 항상 더 낮은 깊이로 가정하기 위한 처리 
 
    if (depth[a] > depth[b]) {
        int tmp = b;
        b = a;
        a = tmp;
    }
 
    /*
        깊이가 다른 경우 맞춰주고 조상을 찾아야 한다. 
    */
 
    int i = 20;
    while(i>=0) {
        if (depth[b] - depth[a] >= (1<<i)) {
            b = parent[b][i]; //b의 조상으로 온다음 다시 비교 
        }
        i--;
    }
 
    if (a == b) return a; //a가 b의 조상임 
 
    i = 20;
    while(i>=0) {
        if (parent[a][i] != parent[b][i]) {
            a = parent[a][i];
            b = parent[b][i];
        }
        i--;
    }
 
    return parent[a][0];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
 
    cin >> n;
    //노드 개수 
    int a, b;
    for (int i = 1; i < n; i++) {
        //간선의 개수 -1 = 노드의 개수
        cin >> a >> b;
 
        edges[a].push_back(b);
        edges[b].push_back(a);
        //서로 이어준다. 
    }
 
    //전처리 
    bfs();
    //트리 만들기 
    setParent(n); 
    //조상들을 dp로 넣어준다. 
 
    cin >> m;
    //알고싶은 애들 입력 받기 
    for (int i = 0; i<m; i++) {
        cin >> a >> b;
 
        cout << lca(a, b) << '\n';
    }
    return 0;
}