[JavaScript] 백준 11725 - 트리의 부모 찾기

목차
1. 문제 풀이
2. 전체 코드 (+시간 복잡도)

---

 

1. 문제 풀이

트리의 부모를 찾기 위해, bfs를 순회하며 부모를 방문 표시 대신 적어주면 된다.

 

1) 인접한 노드들을 edges 배열에 저장

 

2) bfs 코드

- shift 연산 대신 left 변수를 사용하여 시간 복잡도를 줄였다.

- 루트 노드의 부모는 없기 때문에 -1을 저장한다.

- 노드를 순회하면서 해당 노드(cur)와 연결된 "다음 노드(next) 중에서 부모 노드가 없다면"

   👉다음 노드(next)는 현재 노드(cur)의 자식이 된다.

 

 

2. 정답 코드

const fs = require("fs");
const input = fs.readFileSync("./example.txt", "utf8").trim().split("\n");

// 입력
const n = Number(input[0]);
const rawEdges = input.slice(1, n).map((line) => line.split(" ").map(Number));

const edges = Array.from({ length: n + 1 }, () => []);
rawEdges.map(([a, b]) => {
  edges[a].push(b);
  edges[b].push(a);
});

let left = 0;
const q = [1]; // 루트 노드
const parents = Array.from({ length: n + 1 }, () => 0); // 부모 가리키는 배열 초기화(0)
parents[1] = -1; // 루트 노드는 부모가 없으므로 -1 저장

while (left < q.length) {
  const cur = q[left++];

  for (let next of edges[cur]) {
    if (parents[next] == 0) {
      q.push(next);
      parents[next] = cur; // 부모 표시
    }
  }
}

parents.slice(2).forEach((v) => console.log(v));

 

시간 복잡도

모든 노드를 순회하는 데 걸리는 시간은 O(N)이고, for 문을 통해 인접한 노드를 찾으므로 O(E)이다.

이를 더하면 O(N + E)이다.

 

제한 조건 N ≤ 100,000 이므로, 시간은 충분하다

 

문제 링크

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