[ 백준 11725 / Node.js ] 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 복사

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1 복사

4
6
1
3
1
4

예제 입력 2 복사

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2 복사

1
1
2
3
3
4
4
5
5
6
6

 

풀이

 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const solution = (input) => {
  const n = +input.shift(); //+input[0]; 도 가능
  const tree = Array.from(Array(n + 1), () => []);
  const parents = new Array(n + 1).fill(0);
  for (let [from, to] of input.map((edge) => edge.split(' ').map(Number))) {
    tree[from].push(to);
    tree[to].push(from);
  }
 
  const queue = [];
  parents[1] = 1;
  for (let next of tree[1]) {
    // 1이 시작이고 child 노드를 넣고 parents[child]엔 부모노드의 값을 넣어준다.
    parents[next] = 1;
    queue.push(next);
  }
  while (queue.length) {
    const cur = queue.shift();
    for (let next of tree[cur]) {
      if (!parents[next]) {
        parents[next] = cur; // 부모 노드의 값을 넣어준다.
        queue.push(next);
      }
    }
  }
  return parents.slice(2).join('\n');
};
 
console.log(solution(input));