[백준BOJ] 15480_LCA와 쿼리

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

15480번: LCA와 쿼리

---

 

{root, a} = v1

{root, b} = v2

{a,b} = v3

라고 하였을때

depth[v1], depth[v2], depth[v3] 중 가장 큰 노드가 답이 된다.

 

case 1 ) a 와 b 둘다 root의 자손일 경우

case 2) a 또는 b 만 root의 자손일 경우

case 3 ) a와 b 둘다 root의 자손이 아닐 경우 

 

의 case를 생각해보며 식을 적용해보면 왜 그러한지 알 수 있다.

 

---

#include <iostream>
#include <vector>
#include <algorithm>
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][20];

vector<pair<int, int> > tmp; // first : depth, second : node
bool cmp(pair<int, int> a, pair<int, int> b) {
     return a.first > b.first;
}

void dfs(int now, int prev, int prevDepth) {
     visit[now] = true;
     par[now][0] = prev;
     depth[now] = prevDepth;
     
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i]] == false) {
               dfs(vec[now][i], now, prevDepth + 1);
          }
     }
}

int lca(int x, int y) {
     if (depth[x] > depth[y]) swap(x, y);
     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if ((diff >= (1 << i))) y = par[y][i];
     }
     if (x == y) return x;
     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; 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, 1, 0);
     for (int i = 1; i <= 19; i++) {
          for (int j = 1; j <= N; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
          }
     }
     int M, ret; cin >> M;
     for (int i = 0; i < M; i++) {
          int root, a, b; cin >> root >> a >> b;
          int root_a, root_b, a_b;
          root_a = lca(root, a);
          root_b = lca(root, b);
          a_b = lca(a, b);
          tmp.push_back({ depth[root_a], root_a });
          tmp.push_back({ depth[root_b], root_b });
          tmp.push_back({ depth[a_b], a_b });
          sort(tmp.begin(), tmp.end(), cmp);
          cout << tmp[0].second << "\n";
          tmp.clear();
     }
}

---

 

논리적으로 뭔가 해보려고 한참을 고민하다 결국 구글링으로 해답을 찾아본 문제이다.

여러 솔루션들을 보았는데, 논리적 설명보단 테스트케이스를 통해 식을 유추한뒤에

답을 도출해낸 방식이 대다수 이다.

방법이 쉽게 생각나지 않는다면, 테스트 케이스 그대로 따라해보면서 식을 유도하는 것도

실력의 일부가 되는 것 같다.