가장 가까운 공통 조상

가장 가까운 공통 조상

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

문제 설명

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Ancestor)은 다음과 같이 정의됩니다.

두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

예제 입력

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

예제 출력

4
3

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "/dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  let idx = 1;
  const T = Number(input[0]);
  let result = [];

  for (let tc = 0; tc < T; tc++) {
    const N = Number(input[idx++]);

    const graph = Array(N + 1).fill(0);

    // 부모 관계 입력
    for (let i = 0; i < N - 1; i++) {
      const [a, b] = input[idx + i].split(" ").map(Number);
      graph[b] = a;
    }

    // A, B 라인 읽기
    const [A, B] = input[idx + N - 1].split(" ").map(Number);

    // 다음 테스트케이스를 위해 idx 이동
    idx += N;

    // A 조상들 저장
    const set = new Set();
    const dfs1 = (a) => {
      if (a === 0) return;
      set.add(a);
      dfs1(graph[a]);
    };
    dfs1(A);

    // B를 위로 탐색
    let answer = null;
    const dfs2 = (b) => {
      if (b === 0) return;
      if (set.has(b)) {
        answer = b; // 공통 조상 발견
        return;
      }
      dfs2(graph[b]);
    };
    dfs2(B);

    result.push(answer);
  }

  console.log(result.join("\n"));
};

solution(input);

아이디어 / 접근법

1. 조상을 저장하기 위한 set 선언
2. A 의 조상 저장
3. B 의 조상 탐색 하면서 Set에 존재하면 배열에 저장

후기

음 어려운 문제는 아니었음 단순히 dfs 2번 돌려서 조상 찾고 조상 존재하면 반환하면 끝인 문제