백준1068 - 트리 (DFS) node.js

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

해당 문제는 각 노드의 부모 노드를 담은 데이터와 삭제할 노드가 주어진다. 그리고 삭제할 노드를 제외하였을 때의 자식의 개수가 0인 리프 노드의 갯수를 출력해야 한다. 

 

문제 해결 방식

최대한 단순하게 생각했다.

DFS을 통해 순차적으로 노드들을 방문하되, 각 노드가 가진 자식 수를 찾아 저장하는 방식을 택했다. (이때, 여기서 자식 수는 삭제할 노드를 포함하지 않은 수다.)

이후 노드가 가진 자식 수가 0인 경우(리프 노드인 경우)의 갯수를 헤아려 반환했다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const [[n], arr, [t]] = data.map((el) => el.split(" ").map(Number));
  const graph = Array.from({ length: n }, () => []);

  let root;
  arr.forEach((el, idx) => {
    if (el !== -1) graph[el].push(idx);
    else root = idx; // -1 인 경우 최정점이자 시작점
  });

  const result = DFS(graph, root, t);
  console.log(result);
}

function DFS(graph, root, target) {
  // 자식 노드를 담는 배열
  const visited = Array.from({ length: graph.length }, () => false); 
  const stack = [root];

  let stackIdx = 0;
  while (stackIdx < stack.length) {
    const node = stack[stackIdx++];
    if (visited[node] || node == target) continue;
    
    // 삭제할 노드를 제외한 나머지 자식 노드를 저장
    visited[node] = graph[node].filter((el) => el !== target).length;

    graph[node].forEach((next) => {
    // 일반적 DFS 탐색이라면, 다음 자식 노드를 역정렬하여 stack에 삽입해야 하나, 
    // 단지 리프 노드 갯수를 원하는 문제이기에 정렬하지 않음
    // 삭제할 노드를 포함하지 않고 stack에 자식 노드 추가하여 진행
      if (!visited[next] || next !== target) stack.push(next);
    });
  }
  
  // 자식 노드의 수가 0인 것의 갯수를 헤아려 반환
  return visited.filter((el) => el === 0).length;
}

solution(input);