Lowest Common Ancestor

최소 공통 조상 (Lowest Common Ancestor)

관련 문제

백준.1761.정점들의 거리

백준.11438.LCA 2

필요한 자료구조

struct Node {
  int to, weight;
};

원리

LCA를 이용하면 각 트리들의 최소 공통 조상을 구할 수 있다.

노드 A와 B의 높이를 맞춰준 뒤, 한단계씩 올라가며 조상을 찾는 방식이다.

이전에 재귀함수를 이용해 각 노드들의 부모를 갱신해야 하는데, 이를 위해서 다음과 같은 배열들이 필요하다.

// node : 노드의 최대 개수 (MAX)
// level : log_w(MAX) + 1 (MAX_LEVEL)

bool visited[node];  // 노드 방문 여부
int parents[node][level]; // 배열(node: 정점번호 level: 2^level번째 조상을 의미)
int depths[node]; // node의 높이가 몇인지
int distArray[node];   // 루트부터 각 노드들 까지의 거리

재귀함수와 반복문을 이용해 초기값을 설정한다.

// distance 부분은 상황에 따라서 고려
void recursive(int current, int depth, int distance) {
  visited[current] = true;
  depths[current] = depth;
  distArray[current] = distance;

  for (int next : graph[current]) {
    if (visited[next]) continue;

    parents[next][0] = current;
    recursive(next, depth + 1, distance + weights[current]);
  }
}

recursive(rootNode, 0); // 루트노드, 0
for (int level = 1; level <= MAX_LEVEL; level++) {
  for (int node = 1; node <= N; node++) {
    int parent = parents[node][level - 1];
    parents[node][level] = parents[parent][level - 1];
  }
}

최소 공통 조상을 찾는 법은 다음과 같다.

int lowestCommonAncestor(int first, int second) {
  // 첫번째가 자식 노드 높이를 더 낮도록 설정
  if (depths[first] > depths[second]) {
    swap(first, second);
  }

  // 높이를 맞춰줌
  for (int level = MAX_LEVEL; level >= 0; level--) {
    if (depths[second] - depths[first] >= (1 << level)) {
      second = parents[second][level];
    }
  }

  if (first == second) {
    return first;
  }
  for (int level = MAX_LEVEL; level >= 0; level--) {
    if (parents[first][level] != parents[second][level]) {
      first = parents[first][level];
      second = parents[second][level];
    }
  }

  return parents[first][0];
}