[백준] 가장 가까운 공통 조상 #3584

후기

풀이 자체는 쉬웠다.
간선에 parent와 children이라는 변수를 저장해서 셋팅한 후에 찾고자하는 두 노드의 공통 조상을 찾기 위해 첫 번째 target1의 공통 조상을 모두 set 자료구조에 담고, 이후 두 번째 target2의 공통 조상을 탐색하면서 해당 조상이 set에 이미 저장된 조상인지 확인한 후에 출력했다.
구현력 자체가 문제인거지 생각자체는 쉬웠던 풀이.

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const solution = (N, data) => {
  const arr = Array.from(Array(N + 1), () => ({
    parent: null,
    children: new Array(),
  }));
  for (let i = 0; i < N - 1; i++) {
    const [parent, child] = data[i];
    arr[parent].children.push(child);
    arr[child].parent = parent;
  }
  const [target1, target2] = data.pop();
  const cache = new Set();
  let tmp = target1;
  while (tmp) {
    cache.add(tmp);
    tmp = arr[tmp].parent;
  }
  tmp = target2;
  while (tmp) {
    if (cache.has(tmp)) {
      answer += `${tmp}\n`;
      break;
    }
    tmp = arr[tmp].parent;
  }
};

let answer = '';
let T = Number(input[0]);
let cur = 1;
while (T--) {
  const N = Number(input[cur++]);
  const data = input.slice(cur, cur + N).map((v) => v.split(' ').map(Number));
  cur += N;
  solution(N, data);
}

console.log(answer);