[알고리즘/백준/11725] 트리의 부모 찾기(DFS, BFS, 백준 console 시간 초과 해결)

문제

---

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

11725번: 트리의 부모 찾기

 

풀이

---

그래프를 입력 받아 인접 리스트를 만들고, 해당 리스트를 DFS와 BFS로 순회하면서 [부모, 자식]을 배열에 저장한다.

자식을 기준으로 sort한 다음 부모만 map으로 추출하여 answer를 구한다.

 

for문에서 배열을 순회하며 console.log()를 했더니 시간 초과가 났다.

백준에서는 conosole로 답을 출력할 때 한 번에 모아서 처리해야 한다는 점에 유의해야겠다.

 

또 #1, #2처럼 배열에 따로 [부모, 자식]을 저장해서 sort하는 것보다 #3처럼 parents 배열을 만들어 자식 인덱스에 부모를 저장하는 것이 시간과 메모리 측면에서 더 효율적이다.

 

 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const n = +N;
const pairs = arr.map((pair) => pair.split(" ").map(Number));

let graph = Array.from({ length: n + 1 }, () => []);
let ch = Array.from({ length: n + 1 }, () => 0);
let family = [];

// 인접 리스트
for (let [s, e] of pairs) {
  graph[s].push(e);
  graph[e].push(s);
}

function DFS(v) {
  for (let i = 0; i < graph[v].length; i++) {
    const nv = graph[v][i];
    if (ch[nv] === 0) {
      ch[nv] = 1;
      family.push([nv, v]); // [자식, 부모]
      DFS(nv);
    }
  }
}

ch[1] = 1;
DFS(1);

const answer = family
  .sort(([a], [b]) => a - b)
  .map(([child, parent]) => parent);

console.log(answer.join("\n"));

 

#2 BFS

let graph = Array.from({ length: n + 1 }, () => []);
let ch = Array.from({ length: n + 1 }, () => 0);
let q = [];
let family = [];

// 인접 리스트
for (let [s, e] of pairs) {
  graph[s].push(e);
  graph[e].push(s);
}

ch[1] = 1;
q.push(1);

while (q.length) {
  const v = q.shift();

  for (let i = 0; i < graph[v].length; i++) {
    const nv = graph[v][i];

    if (ch[nv] === 0) {
      ch[nv] = 1;
      family.push([nv, v]); // [자식, 부모]
      q.push(nv);
    }
  }
}

const answer = family
  .sort(([a], [b]) => a - b)
  .map(([child, parent]) => parent);

console.log(answer.join("\n"));

 

#3 parents 배열 활용하기

let graph = Array.from({ length: n + 1 }, () => []);
let ch = Array.from({ length: n + 1 }, () => 0);
let parents = Array.from({ length: n + 1 }, () => 0);

// ...생략 

function DFS(v) {
  for (let i = 0; i < graph[v].length; i++) {
    const nv = graph[v][i];
    if (ch[nv] === 0) {
      ch[nv] = 1;
      parents[nv] = v; //parents[자식] = 부모
      DFS(nv);
    }
  }
}

ch[1] = 1;
DFS(1);
console.log(parents.slice(2).join("\n"));