(3584) 가장 가까운 공통 조상

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

단계별로 풀어보기

47단계(최소 공통 조상) 1번째

 

 

 

최소 공통 조상(LCA)를 구하는 문제.

만약 두 노드의 깊이가 같다고 하면, 매 단계마다 각각의 노드의 부모로 거슬러 올라가면 어느 순간 같은 노드에서 만나는 경우가 생길 것이고, 이때 노드가 LCA이다. 두 노드의 깊이가 다르다면 깊이가 같아질 때까지 더 깊은 노드만 부모로 거슬러 올라간다.

이 구현을 위해 입력을 전부 받은 뒤 루트 정점을 찾아 DFS 등을 이용해 트리를 순회하며 각 노드의 부모와 깊이를 저장할 필요가 있다.

 

 

 

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

int solve(){
  int n;
  
  cin >> n;
  
  vector adj(n+1, vector<int>());
  vector<pair<int,int>> node(n+1);
  
  for(int i=1;i<n;i++){
    int a, b;
    
    cin >> a >> b;
    
    node[b].first= a;
    adj[a].push_back(b);
  }
  
  auto dfs= [&](auto self, int now, int prev) -> void {
    for(int next:adj[now]){
      if(next==prev)  continue;
      
      node[next].second= node[now].second+1;
      self(self, next, now);
    }
  };
  
  for(int i=1;i<=n;i++){
    if(!node[i].first)  dfs(dfs, i, 0);
  }
  
  int x, y;
  
  cin >> x >> y;
  
  while(node[x].second>node[y].second)  x= node[x].first;
  while(node[x].second<node[y].second)  y= node[y].first;
  
  while(x!=y){
    x= node[x].first;
    y= node[y].first;
  }
  
  return x;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }
  
  return 0;
}

 

 

 

다만 이 문제처럼 트리 하나마다 질문 쿼리가 1번 주어져 시간복잡도와 재사용성을 고려하지 않아도 되는 경우에는 더 편한 방법이 있다.

첫번째 노드에서 루트까지 계속 부모 정점으로 거슬러 올라가며 처음 자신을 포함한 모든 방문한 노드에 방문 표시를 한다.

이제 두번째 노드에서 부모 정점으로 거슬러 올라가며 처음으로 방문 표시가 되어있는 노드에 도달하면 그 노드가 LCA가 된다.

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

int solve(){
  int n;
  
  cin >> n;
  
  vector<int> parent(n+1);
  vector<bool> visited(n+1);
  
  for(int i=1;i<n;i++){
    int a, b;
    
    cin >> a >> b;
    
    parent[b]= a;
  }
  
  int x, y, prev;
  
  cin >> x >> y;
  
  visited[x]= true;
  while(parent[x]){
    x= parent[x];
    visited[x]= true;
  }
  
  while(!visited[y]){
    y= parent[y];
  }
  
  return y;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }
  
  return 0;
}