[프로그래머스] 카카오 - 길 찾기 게임

문제

2019 카카오 블라인드 채용 - 길 찾기 게임

https://school.programmers.co.kr/learn/courses/30/lessons/42892

 

 

풀이

설명

노드들로 구성된 이진트리를 전위 순회, 후위 순회환 결과를 구하는 문제입니다.

 

y 값이 큰 순서대로, x 값이 작은 순서대로 정렬한 후, 이진트리를 구성한 다음, 순회를 하면 됩니다.

 

예시 코드

function solution(nodeinfo) {
  const nodes = nodeinfo.map((info, index) => ({
    x: info[0],
    y: info[1],
    index: index + 1,
  }));

  nodes.sort((a, b) => b.y - a.y || a.x - b.x);

  const preOrder = [];
  const postOrder = [];

  const root = buildTree(nodes[0], -Infinity, Infinity);
  traverse(root);

  return [preOrder, postOrder];

  function buildTree(node, leftBound, rightBound) {
    if (!node) return null;

    const leftNode = nodes.find(
      (n) => n.x < node.x && n.y < node.y && n.x > leftBound && n.x < rightBound
    );
    const rightNode = nodes.find(
      (n) => n.x > node.x && n.y < node.y && n.x > leftBound && n.x < rightBound
    );

    return {
      node: node,
      left: buildTree(leftNode, leftBound, node.x),
      right: buildTree(rightNode, node.x, rightBound),
    };
  }

  function traverse(node) {
    if (!node) return;

    preOrder.push(node.node.index);
    traverse(node.left);
    traverse(node.right);
    postOrder.push(node.node.index);
  }
}