[백준] 11725번 트리의 부모 찾기 - JavaScript(NodeJS)

문제

11725번: 트리의 부모 찾기

풀이

트리의 루트는 1로 정해져 있다.

2번 노드부터 순서대로 각 노드의 부모 노드의 번호를 출력하면 된다.

각 입력(1 6, 6 3, 3,5 ... )에 대해서 무방향 트리임을 고려해서 입력을 받는다.

BFS 너비우선탐색을 이용해보자.

 

1부터 BFS로 조회하면서 방문을 위한 체크 배열에는, 인덱스(자식 노드)에 값(부모 노드)를 입력한다.
부모 노드는 최소 1의 값을 가지므로, 방문 여부 판별에 이용할 수 있다.

 

BFS가 끝나면 체크 배열에서 2번 인덱스부터 출력한다.

 

 

코드를 작성해보자.

 

코드

const sol = (input) => {
  const N = +input[0];
  input = input.slice(1);
  const tree = Array.from({ length: N + 1 }, () => new Array());
  input.map((val) => {
    const [from, to] = val.split(" ").map(Number);
    tree[from].push(to);
    tree[to].push(from); // 무방향 트리이므로 A->B, B->A 정보를 모두 넣어준다.
  });

  let check = Array.from({ length: N + 1 }, () => 0);
  function bfs() {
    const queue = [];
    check[1] = 1;
    for (let next of tree[1]) { // next(child) 노드 값의 인덱스에 1(부모 노드)값을 넣어주고, 큐에 넣어준다.
      check[next] = 1;    
      queue.push(next);
    }
    while (queue.length) {
      const node = queue.shift();
      for (let next of tree[node]) { // 노드를 순회하면서, 방문한 노드라면 건너뛴다.
        if (check[next]) continue;
        check[next] = node; // 위와 같이 next 인덱스에는 node(부모 노드)값을 넣는다.
        queue.push(next);
      }
    }
  }
  bfs();

  check = check.slice(2);
  let result = "";
  check.map((v) => (result += `${v}\n`)); // 체크 배열의 2번 인덱스(2번 노드)부터 출력한다.
  return result;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });