백준 11725 트리의 부모 찾기

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const solution = (input) => {
  const n = +input.shift();
  const tree = Array.from(Array(n + 1), () => []);
  const check = new Array(n + 1).fill(0);
  for (let [from, to] of input.map((e) => e.split(" ").map(Number))) {
    tree[from].push(to);
    tree[to].push(from);
  }

  const queue = [];
  check[1] = 1;
  for (let next of tree[1]) {
    // 1이 시작이고 child 노드를 넣고 check[child]엔 부모노드의 값을 넣어준다.
    check[next] = 1;
    queue.push(next);
  }
  while (queue.length) {
    const cur = queue.shift();
    for (let next of tree[cur]) {
      if (!check[next]) {
        check[next] = cur; // 부모 노드의 값을 넣어준다.
        queue.push(next);
      }
    }
  }
  // console.log(check);
  return check.slice(2).join("\n");
};

console.log(solution(input));

• 인접 리스트 형태로 tree를 생성한다.
• bfs를 이용하고 check 배열에 부모노드를 저장한다.
• 예를 들어 check 노드 4번 인덱스의 값이 5이면 3번노드의 부모노드가 5라는 뜻이다.