[백준BOJ] 11437_LCA (C++)

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

11437번: LCA

---

입력을 받은후

1. DFS

입력을 받은뒤, DFS를 돌면서 ( 문제에서 root는 1번노드 ) depth와 부모를 저장해준다.

void dfs(int now, int nowDepth,int prev) {
     visit[now] = true; // visit
     depth[now] = nowDepth; // 현재 노드의 깊이
     par[now][0] = prev; // 현재 노드의 [0]번째 부모( 바로 윗 부모 )
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i]] == false) {
               dfs(vec[now][i], nowDepth + 1,now);
          }
     }
}

2. 부모의 parser_table 생성

반복문으로 parser_table을 생성한다.

주석으로 자세한 설명을 해놓았다.

   // 2 ^ 19 번째 부모는 입력조건보다 한참 크다, 딱 맞게(타이트하게) 부모의 깊이를 잡으려면
     // tree가 오른쪽으로만 늬여진 일렬로된 트리라고 가정한다면, (k = log(노드갯수)) 에서 par[노드수][k]로 설정하면 된다.
     for (int j = 1; j <= 19; j++) {
          for (int i = 1; i <= N; i++) {
               // i번 노드의 2^j번째 부모 = i의 2^(j-1)번쨰 부모의 2^(j-1) 부모
               // example )
               // par[1][1] = par[par[1][0]][0] : 1번 노드의 (2^1)번째 부모 = 1번노드의 (0)번째 부모의 (0)번째 부모( 즉 부모의 부모 )
               // par[1][2] = par[par[1][1]][1] : 1번 노드의 (2^2)번째 부모 = 1번노드의 (2^1)번쨰 부모의 (2^1)번째 부모 ( 즉, 증조부모의 증조부모 )
               // ...
               par[i][j] = par[ par[i][j - 1]][j - 1];
          }
     }

3. lca 함수

(주석 참고)

int lca(int x, int y) {
     // 깊이가 더 깊은 놈 ( 루트와 거리가 먼놈이 y가 된다 )
     if (depth[x] > depth[y]) SWAP(x, y);

     // y는 현재 더 깊이 있음으로 y를 x의 depth만큼 올려줘야 한다.
     // example)
     // x와 y가 diff가 5만큼 차이 난다고 가정하면
     // y에서 par[y][2] : y의 ( 2^2 ) 번째 부모로 올라감
     // y에서 par[y][0] : y의 ( 1^1 ) 번째 부모로 올라감
     // total 5만큼 높이가 올라가게 된다.
     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) y = par[y][i];
     }
     
     // depth를 맞췄는데 같은 노드번호라면 리턴
     if (x == y) return x;
     
     // 부모가 같을테까지 같은 depth를 똑같이 올려준다
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     // 같아진 부모의 노드번호를 리턴해준다.
     return par[x][0];
}

---

전체코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define MAX_N 100001
#define SWAP(a,b) {int t = b; b = a; a = t;}

vector<int> vec[MAX_N];
bool visit[MAX_N];
int depth[MAX_N];
int par[MAX_N][21];

void dfs(int now, int nowDepth,int prev) {
     visit[now] = true; // visit
     depth[now] = nowDepth; // 현재 노드의 깊이
     par[now][0] = prev; // 현재 노드의 [0]번째 부모( 바로 윗 부모 )
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i]] == false) {
               dfs(vec[now][i], nowDepth + 1,now);
          }
     }
}

int lca(int x, int y) {
     // 깊이가 더 깊은 놈 ( 루트와 거리가 먼놈이 y가 된다 )
     if (depth[x] > depth[y]) SWAP(x, y);

     // y는 현재 더 깊이 있음으로 y를 x의 depth만큼 올려줘야 한다.
     // example)
     // x와 y가 diff가 5만큼 차이 난다고 가정하면
     // y에서 par[y][2] : y의 ( 2^2 ) 번째 부모로 올라감
     // y에서 par[y][0] : y의 ( 1^1 ) 번째 부모로 올라감
     // total 5만큼 높이가 올라가게 된다.
     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) y = par[y][i];
     }
     
     // depth를 맞췄는데 같은 노드번호라면 리턴
     if (x == y) return x;
     
     // 부모가 같을테까지 같은 depth를 똑같이 올려준다
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     // 같아진 부모의 노드번호를 리턴해준다.
     return par[x][0];
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N;
     for (int i = 0; i < N-1; i++) {
          int a, b;
          cin >> a >> b;
          vec[a].push_back(b);
          vec[b].push_back(a);
     }
     dfs(1, 0, 1);

     // 2 ^ 19 번째 부모는 입력조건보다 한참 크다, 딱 맞게(타이트하게) 부모의 깊이를 잡으려면
     // tree가 오른쪽으로만 늬여진 일렬로된 트리라고 가정한다면, (k = log(노드갯수)) 에서 par[노드수][k]로 설정하면 된다.
     for (int j = 1; j <= 19; j++) {
          for (int i = 1; i <= N; i++) {
               // i번 노드의 2^j번째 부모 = i의 2^(j-1)번쨰 부모의 2^(j-1) 부모
               // example )
               // par[1][1] = par[par[1][0]][0] : 1번 노드의 (2^1)번째 부모 = 1번노드의 (0)번째 부모의 (0)번째 부모( 즉 부모의 부모 )
               // par[1][2] = par[par[1][1]][1] : 1번 노드의 (2^2)번째 부모 = 1번노드의 (2^1)번쨰 부모의 (2^1)번째 부모 ( 즉, 증조부모의 증조부모 )
               // ...
               par[i][j] = par[ par[i][j - 1]][j - 1];
          }
     }
     cin >> M;
     for (int i = 0; i < M; i++) {
          int a, b; cin >> a >> b;
          cout << lca(a, b) << "\n";
     }
}