백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 1068 , 트리

백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 1068 , 트리

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


덧붙일 말 🏷️
트리 기본 문제로 적합하다. 
이진트리로 착각하는 분들이 있는데, 문제 명시에는 이진 트리라고 나와있지 않다. 주의.
77%에서 많이 틀린다고 질문게시판에 글이 많았다. 
해당 로직으로는 문제없이 통과하였다.

 

 

문제 출처 🏠

 

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

1068번: 트리

 

 

 

요구사항 📋

첫째 줄에 N이 주어짐.
둘째 줄에 0부터~N-1 까지의 각 노드의 부모노드가 담긴 숫자들이 주어짐.
-1이라면 루트노드를 뜻함.
마지막 줄에 제거할 노드가 주어짐.
노드를 제거하게 되면 그 자식노드들은 다 삭제됨.
제거 후 남은 트리에서의 리프 노드 개수를 출력.

 

 

 

 

해결 전략 📝

삭제한 노드의 자식노드들을 탐색해야하니 양방향 그래프말고 자식 노드를 가르키는 단방향 그래프로 만들어야겠음.

 

삭제 노드의 자식노드가 담긴 배열을 빈배열로 초기화 시켜주면 타고 내려가는 것이 자연스럽게 막아진다.

 

대신, 삭제 노드의 부모노드에는 삭제노드에 대한 정보가 아직 담겨있는 상태이므로, 삭제 노드의 부모노드로 한번 거슬러 올라가서 삭제 시킬 노드를 삭제시키는 작업이 추가적으로 해주자.

 

 

 

 

기능 목록 📲

1. 자식노드를 타고 가면서 리프 노드에 도착했을 때 카운트해 주는 함수. => cntLeafNode

 

 

예외사항 ⚠️

1. 처음 부터 부모 노드를 삭제시켜 버리는 경우. => 바로 0 리턴시켜버리기.

 

 

---

정답 💯

 

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.trim());

const t = input.shift();
const d = input.pop();
const Nums = input[0].split(" ").map(Number);

function solution(T, parentNodes, D) {
  let tree = Array.from({ length: T + 1 }).map(() => []);
  let [start, cnt] = [0, 0];
  parentNodes.map((parent, idx) => {
    if (parent !== -1) tree[parent].push(idx);
    else start = idx;
  });

  if (start === D) return 0;

  tree[parentNodes[D]] = tree[parentNodes[D]].filter(
    (childNode) => childNode !== D
  );
  tree[D] = [];

  function cntLeafNode(startNode) {
    let childNodes = tree[startNode];
    if (childNodes.length === 0) {
      cnt += 1;
      return;
    }
    childNodes.map((child) => {
      cntLeafNode(child);
    });
  }
  cntLeafNode(start);
  return cnt;
}

console.log(solution(Number(t), Nums, Number(d)));

 

 

 

 

느낀점 🧑‍💻

이진트리라 생각해도 자식 노드로 이어지는 간선을 끊고, 부모노드에서 흔적을 지워주면 크게 문제 없을 것 같다.