백준 3584 : 가장 가까운 공통 조상 - javascript(dfs)

문제 출처 

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

 

정답 풀이 

이거는 사실 입력처리 하는 것이 까다로웠던 것 같다. 

 

문제를 푸는 핵심은 

- 각 노드의 부모를 배열에 저장을 한다. 

- 하나 노드의 모든 부모를 배열 (= 조상 배열)로 정리한다. 

  - 함수로 만들 것 

- 비교해야 하는 노드 두개의  조상 배열을 비교한다. 

- 뒤에서부터 비교해서 일치하지 않을 때 그때의 조상이 답이 된다. 

 

 

readline 모듈을 사용하여 입력을 한 줄씩 받아 배열 input에 저장한다. 

입력이 완료되면 on('close') 이벤트가 실행되어 본격적으로 문제를 처리한다. 

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
rl.on('line', function(line) {
    input.push(line);
}).on('close', function() {

 

첫번째 줄에 주어진 테스트 케이스 수 T를 읽는다. 

각 테스트 케이스마다 노드의 수 N을 입력받고, 노드들의 부모 정보를 저장하기 위한 배열 parent를 초기화한다. 

const T = parseInt(input[0]);  // 테스트 케이스 수
let idx = 1;

for (let t = 0; t < T; t++) {
    const N = parseInt(input[idx]);  // 노드의 수
    let parent = Array(N + 1).fill(0);  // 부모 정보를 저장하는 배열
    idx++;

 

N-1개의 간선 정보를 입력받아 트리 구조를 구성한다. 

각 노드 v의 부모가 u라는 정보를 parent 배열에 저장한다. 이를 통해 트리 구조가 간접적으로 표현된다. 

    for (let i = 0; i < N - 1; i++) {
        const [u, v] = input[idx].split(' ').map(Number);
        parent[v] = u;  // v의 부모는 u
        idx++;
    }

 

공통조상을 찾아야 할 두 노드를 입력받는다. 

    const [node1, node2] = input[idx].split(' ').map(Number);
    idx++;

 

이 함수는 주어진 노드에서 루트 노드까지의 부모 경로를 역순으로 저장한 배열을 반환한다. 

node가 0이 될 때까지 부모를 따라 올라가며 경로를 저장한다. 이는 두 노드 간의 경로를 비교하기 위함이다. 

 

    function findAncestors(node) {
        let ancestors = [];
        while (node !== 0) {
            ancestors.push(node);
            node = parent[node];
        }
        return ancestors;
    }

 

node1과 node2의 부모 경로를 각각 구한다. ancestors1과 ancestors2 배열에는 각 노드에서 루트 노드까지의 경로가 역순으로 저장된다. 

 

    const ancestors1 = findAncestors(node1);
    const ancestors2 = findAncestors(node2);

 

두 경로 배열을 역순으로 비교하면서 가장 가까운 공통 조상을 찾는다. 

p1과 p2는 각각 ancestors1과 ancestors2의 마지막 인덱스를 가리키며, 이 두 경로를 뒤에서부터 비교한다. 

두 경로가 동일할 때까지 부모를 계속해서 비교하고, 가장 마지막으로 동일했던 노드를 공통 조상으로 저장한다. 

두 경로의 마지막까지 동일한 노드를 찾고 나면, 그 노드가 가장 가까운 공통 조상이다. 

 

    let lca = 0;
    let p1 = ancestors1.length - 1;
    let p2 = ancestors2.length - 1;

    while (p1 >= 0 && p2 >= 0 && ancestors1[p1] === ancestors2[p2]) {
        lca = ancestors1[p1];
        p1--;
        p2--;
    }

    console.log(lca);

정답 코드 

//해당 노드의 부모 배열을 정리 
//역순으로 탐색을 통해 숫자가 달라질 때의 값을 정답으로 출력

let readline = require('readline')

const rl = readline.createInterface({
    input : process.stdin, 
    output : process.stdout
    })

let input = []; 
rl.on('line', function(line){
    input.push(line)
}).on('close', function(){
      const T = parseInt(input[0])
      let idx = 1
      
      for(let t=0; t<T; t++){
          const N = parseInt(input[idx])
          let parent = new Array(N+1).fill(0);
          idx++
          
          for(let i=0; i<N-1; i++){
             const [u,v] = input[idx].split(' ').map(v => +v)
             parent[v] = u;
             idx++
          }
          
          const [node1, node2] = input[idx].split(' ').map(v => +v)
          idx++; 
          
          function findAncestors(node){
              let result = []; 
              while(node !== 0){
                  result.push(node); 
                  node = parent[node]
              }
              return result
          }
          
          const ancestors1 = findAncestors(node1)
          const ancestors2 = findAncestors(node2)
          
          let answer = 0; 
          let p1 = ancestors1.length-1
          let p2 = ancestors2.length-1
          
          while(p1 >= 0 && p2>=0 && ancestors1[p1] === ancestors2[p2]){
              answer = ancestors1[p1]
              p1--
              p2--
          }
          console.log(answer)
      }
      })