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

🔗 문제 링크

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

11725번: 트리의 부모 찾기

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const edges = input.map(v => v.split(' ').map(Number));
const tree = [...Array(N + 1)].map(() => []);
const relations = [];
edges.forEach(([a, b]) => {
  tree[a].push(b);
  tree[b].push(a);
});

const bfs = () => {
  const visited = Array(N + 1).fill(false);
  visited[1] = true;
  let queue = [1];
  let stack;
  while (queue.length) {
    stack = queue;
    queue = [];
    while (stack.length) {
      const node = stack.pop();
      const children = tree[node];
      if (children) {
        children.forEach(child => {
          if (!visited[child]) {
            visited[child] = true;
            relations[child] = node;
            queue.push(child);
          }
        });
      }
    }
  }
};

bfs();
console.log(relations.slice(2).join('\n'));

주어진 간선 정보를 바탕으로 tree에 인접 배열을 만들어 저장하였다.

BFS를 하면서 queue에 push되는 노드들은 곧 현재 노드의 자식 노드들이다.

이 때, relations에 해당 자식 노드들의 부모를 현재 노드로 저장한다.

BFS가 끝난 뒤, relations의 인덱스 2부터 개행문자로 묶어서 출력하였다.