[백준 | 실버 2 | JavaScript] 11725번, 트리의 부모 찾기

 

Link

11725번 - 트리의 부모 찾기

 

---

문제

풀이

(1)

var input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input[0]);
let graph = Array.from({ length: N + 1 }, () => []);

// 트리의 간선은 N-1개이므로 해당 줄만 처리
for (let i = 1; i <= N - 1; i++) {
  let [a, b] = input[i].split(" ").map(Number);
  graph[a].push(b);
  graph[b].push(a);
}

let parent = Array(N + 1).fill(0);
let visited = Array(N + 1).fill(false);

// DFS를 재귀로 구현 (대형 입력의 경우 스택 오버플로우 주의)
function dfsRecursive(node) {
  visited[node] = true;

  for (let next of graph[node]) {
    if (!visited[next]) {
      parent[next] = node;
      dfs(next);
    }
  }
}

dfsRecursive(1);

console.log(parentsArr.slice(2).join("\n"));

(2)

var input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input[0]);
let graph = Array.from({ length: N + 1 }, () => []);

// 트리의 간선은 N-1개이므로 해당 줄만 처리
for (let i = 1; i <= N - 1; i++) {
  let [a, b] = input[i].split(" ").map(Number);
  graph[a].push(b);
  graph[b].push(a);
}

let parent = Array(N + 1).fill(0);
let visited = Array(N + 1).fill(false);

function dfsStack(node) {
  let stack = [node];

  while (stack.length > 0) {
    let pop = stack.pop();
    if (visited[pop]) continue;

    visited[pop] = true;
    for (let g of graph[pop]) {
      if (visited[g]) continue;
      parent[g] = pop;
      stack.push(g);
    }
  }
}

dfsStack(1);

console.log(parentsArr.slice(2).join("\n"));