백준 - 1068 트리, 15900 나무 탈출

선정 이유

• 21일 금요일 스크럼때 풀지 못했다고 했던 문제(15900 나무 탈출)를 풀게됨

• 지난주 강의에 포함된 트리 자료구조를 이용해 풀 수 있는 문제

• 백준에서 node.js 풀이가 시간 초과가 나오는 경우 소소한 팁 공유

1068 트리

const [[N], parentNodes, [removeNode]] = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : '../../input.txt', 'utf-8')
  .trim()
  .split('\n')
  .map(x => x.split(' ').map(Number));

function solution(N, parentNodes, removeNode) {
  const tree = Array.from({ length: N }, () => []);
  const start = parentNodes.findIndex(x => x === -1);

  if (start === removeNode) return 0;

  parentNodes.forEach((parentNode, i) => {
    if (parentNode !== -1 && parentNode !== removeNode && i !== removeNode) {
      tree[parentNode].push(i);
      tree[i].push(parentNode);
    }
  });

  const visited = Array(N).fill(false);

  return dfs(start, tree, visited);
}

function dfs (start, tree, visited) {
  const stack = [start];
  visited[start] = true;

  let leafCount = 0;

  while (stack.length !== 0) {
    const src = stack.pop();

    if ((src !== start && tree[src].length === 1) || tree[src].length === 0) {
      leafCount += 1;
      continue;
    }

    for (const dst of tree[src]) {
      if (!visited[dst]) {
        visited[dst] = true;
        stack.push(dst);
      }
    }
  }

  return leafCount;
}
console.log(solution(N, parentNodes, removeNode));

• 일반적인 DFS 문제에 리프 노드인지 판별하는 로직을 추가
• 시작이 항상 0번 째 노드일 거라는 생각과 리프 노드를 확인할 때 루트 노드 하나만 남는 경우를 고려하지 못해 시간이 많이 소요됨

if (tree[src].length === 1)

• 주어진 정점을 연결 리스트로 표현하는 그래프 tree 선언

• removeNode는 연결하지 않음

• 방문 기록을 저장할 배열 visited 선언

• DFS 탐색
• 탐색에 사용할 stack 선언
• 리프 노드의 수를 카운팅할 leafCount 선언
• stack의 요소가 없을 때 까지 반복
• 현재 노드가 루트가 아니고, 인접 리스트의 길이가 1이거나 인접 리스트의 길이가 하나도 없는 경우 (연결된 노드가 부모 하나인 경우와 루트 노드 하나만 남는 경우) leafCount 를 +1
• 현재 노드 src와 연결되어 있는 노드 중 방문하지 않은 노드 dst를 탐색
• 해당 노드를 방문 처리 후 stack에 push

• leafCount를 반환

15900 나무 탈출

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : '../../input.txt', 'utf-8')
  .trim()
  .split('\n');


function solution(input) {
  const N = +input[0];
  const tree = Array.from({ length: N + 1 }, () => []);

  for (let i = 1; i< N; i += 1) {
    const [src, dst] = input[i].split(' ');
    tree[+src].push(+dst);
    tree[+dst].push(+src);
  };

  const visited = Array(N + 1).fill(false)

  return dfs(1, tree, visited);
}

function dfs(start, tree, visited) {
  const stack = [[start, 0]];
  visited[start] = true;
  
  let leafDist = 0;

  while (stack.length !== 0) {
    const [src, dist] = stack.pop();

    if (src !== start && tree[src].length === 1) {
      leafDist += dist;
      continue;
    }

    for (const dst of tree[src]) {
      if (!visited[dst]) {
        visited[dst] = true;
        stack.push([dst, dist + 1]);
      }
    }
  }
  return leafDist % 2 === 0 ? 'No' : 'Yes';
}

console.log(solution(input));

• 주어진 정점을 연결 리스트로 표현하는 그래프 tree 선언

• 방문 기록을 저장할 배열 visited 선언

• DFS 탐색
• 탐색에 사용할 stack선언 후 현재 노드와 루트에서 현재 노드까지의 거리를 삽입
• 리프 노드들의 거리를 저장할 leafDist 선언
• stack의 요소가 없을 때 까지 반복
• 현재 노드가 루트가 아니고, 인접 리스트의 길이가 1인 경우 (연결된 노드가 부모 하나인 경우) leafDist 에 현재 노드의 거리를 저장
• 현재 노드 src와 연결되어 있는 노드 중 방문하지 않은 노드 dst를 탐색
• 해당 노드를 방문 처리
• stack에 해당 노드 dst와 현재 노드까지의 거리를 나타내는 dist에 +1을 하여 push

• leafDist 가 짝수이면 No 홀수면 Yes 출력

그러나 시간 초과가 계속해서 발생함

• 입력 데이터를 가공하는 과정에서 문제가 있는 것이라 판단함

• input을 받는 과정에서 형변환을 위한 중첩된 고차함수를 제거하고 매 순회시 형변환을 하도록 수정

.readFileSync(process.platform === 'linux' ? '/dev/stdin' : '../../input.txt', 'utf-8')
  .trim()
  .split('\n')
  .map(x => x.split(' ').map(Number));