[short] 최소공통조상 알고리즘 (Longest Common Ancestor)

 

어떤 한 그래프에서 '모든 정점으로 가는 경로가 존재하고 유일하다' == Tree

이용한 문제들

14942번: 개미

11438번: LCA 2

그래프를 빙자한 트리 문제가 나올 때마다 logN 스케일로 원하는 노드에서 노드값을 구해줘야하는 상황이 있다.

DFS의 성질이나 DP를 이용해서 넘겨주는 방식도 있긴하다만 구현하기가 복잡하다.

그럴 때마다 LCA알고리즘을 써서 ancestor[현재노드][2^i번째 조상]을 저장하면 빠르게 구할 수 있다.

void dfs(int pre, int cur, int level){
  if(vis[cur])return;
  vis[cur]=1;
  for(int i=0;(int)pow(2,i)<level;i++){
    if(i==0) anc[cur][i]=pre;
    else anc[cur][i]=anc[anc[cur][i-1]][i-1];
    // 2^i번째 조상은 현재에서 2^i-1번째 조상의 2^i-1번째 조상이다. (2^i-1 + 2^i-1 == 2^i)
  }
  for(auto i:adj[cur])
    dfs(cur,i,level+1);
}

root를 시작으로 dfs를 돌려주면 셋팅은 끝

이후로는 문제조건에 맞게 돌려주면 된다.

 

14942번에서 이용한 코드

 

for(int i=1;i<=n;i++){
    int cur=i,idx,target=i;
    // 개미가 현재 에너지를 다 써서 갈 수 있는 최대 위치를 구한다
    while(1){
      idx=0;
      for(;anc[target][idx]!=-1;idx++){
        if(prefix[cur]-prefix[anc[target][idx]]<=v[i]) continue;
        else break;
      }
      idx--;
      if(idx==-1)break;
      else target=anc[target][idx];
    }
    cout<<target<<endl;
  }

셋업자체는 쉬운데 원하는 값 찾는게 살짝 까다롭다.

공통조상을 찾는다면 두 정점의 level을 맞추어 주고 같은게 나올 때 까지 올려야하고

14942번과 같이 특정 조건을 만족하는 최대 위치를 구하려면 역시나 while문으로 조건 체크해가면 돌려야한다.

자주 잊어먹어서 기록해둔다.

 

 

추가)

트리는 최악의 경우 O(N)의 시간복잡도를 가질 수 있다.

만약 임의의 두 정점이 양 끝쪽에 위치한다면 level을 맞춰줄 때 하나씩 올리다가는 TLE가 발생한다.

  //level 맞춰주는 과정도 O(logN)으로 접근해야한다.
  if(lev[a]<lev[b]){
    int cur=b;
    for(int i=17;i>=0;i--){
      if(lca[cur][i]!=-1&&lev[lca[cur][i]]>lev[a]) cur=lca[cur][i];
    }
    cur=lca[cur][0];
    b=cur;
  }
  else if(lev[a]>lev[b]){
    int cur=a;
    for(int i=17;i>=0;i--){
      if(lca[cur][i]!=-1&&lev[lca[cur][i]]>lev[b]) cur=lca[cur][i];
    }
    cur=lca[cur][0];
    a=cur;
  }