[JS] LCA

1. 그래프 만들기

/**
 * @description 출발 노드, 도착 노드를 포함한 이차원 배열을 인자로 받습니다.
 * @param {number} n 노드 갯수 
 * @param {[number, number][]} edges 
 */
function makeConnection(n, edges) {
  const con = Array.from({ length: n }, () => []);

  edges.forEach(([node1, node2]) => {
    con[node1].push(node2);
    con[node2].push(node1);
  });

  return con;
}

2. 깊이와 조상

/**
 * @description 2개 이상의 노드로 이루어지고, 모든 노드가 연결된 인접 리스트를 인자로 받습니다.
 * @param {number} root
 * @param {number[][]} con 
 */
function makeDepth(root, con) {
  const size = con.length;
  const depth = Array(size);
  const ancs = Array.from({ length: size }, () => []);

  const stack = [];
  con[root].forEach((node) => stack.push([node, root]));
  depth[root] = 0;

  while (stack.length) {
    const [cur, parent] = stack.pop();

    depth[cur] = depth[parent] + 1;
    ancs[cur][0] = parent;

    // 모든 조상을 전부 기록하고 탐색하는 것보다, 2의 제곱승의 조상만을 기록하고 탐색하는 것이 핵심
    // ancs[a][b]는 a의 2의 b 제곱승 순서의 조상을 가리킴
    const ancLimit = Math.floor(Math.log2(depth[cur]));
    for (let i = 1; i <= ancLimit; i += 1) {
      const anc = ancs[cur][i - 1];
      ancs[cur][i] = ancs[anc][i - 1];
    }

    con[cur].forEach((node) => {
      if (node !== parent) stack.push([node, cur]);
    });
  }

  return [depth, ancs];
}

3. LCA

/**
 * @description target 노드와 가장 근접한 깊이의 조상 노드를 탐색합니다.
 * @param {number} node
 * @param {number} target 
 * @param {number[][]} ancs
 * @param {number[]} depth 
 */
function getSameDpethAnc(node, target, ancs, depth) {
  let left = 0;
  let right = ancs[node].length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const anc = ancs[node][mid];
    const comp = depth[anc] - depth[target];

    if (comp === 0) return ancs[node][mid];
    if (comp > 0) left = mid + 1;
    else right = mid - 1;
  }

  return ancs[node][right];
}

/**
 * @description target 두 노드의 공통 조상을 탐색합니다.
 * @param {number} a
 * @param {number} b 
 * @param {number[][]} ancs
 * @param {number[]} depth 
 */
function lca(a, b, ancs, depth) {
  // 두 노드의 깊이를 같게합니다.
  let [deep, shallow] = depth[a] < depth[b] ? [b, a] : [a, b];
  while (depth[deep] !== depth[shallow]) {
  	deep = getSameDpethAnc(deep, shallow, ancs, depth);
  }
  
  if (deep !== shallow) {
    for (let i = ancs[deep].length - 1; i >= 0; i -= 1) {
      if (i < ancs[deep].length && this.ancs[deep][i] !== this.ancs[shallow][i]) {
        deep = ancs[deep][i];
        shallow = ancs[shallow][i];
      }
    }
    
    deep = ancs[deep][0];
    shallow = ancs[shallow][0];
  }

  return deep;
}