길 찾기 게임

문제 링크

문제 요약

트리의 조건

• 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
• 모든 노드는 서로 다른 x값을 가진다.
• 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
• 자식 노드의 y 값은 항상 부모 노드보다 작다.
• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

제한사항

• nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
• nodeinfo의 길이는 1 이상 10,000 이하이다.
• nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
• 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
• 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
• 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.

Input

• 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo

output

• 노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return

해결방법

• y를 기준으로 소트를 하면 계층에 따라 나눌 수 있다.

• 노드를 파고 들면서 x값을 이용해 leftNodes와 rightNodes로 나눈다.

  • 첫 노드를 부모로 잡고 나머지 노드를 재귀적으로 분류한다.
• 첫 요소를 호출하는 시점에 따라서 전위 순회와 후위 순회로 분류 가능하다

function solution(nodeinfo) {
  const nodes = nodeinfo
    .map((node, idx) => {
      return { x: node[0], y: node[1], value: idx + 1 }
    })
    .sort((a, b) => {
      return b.y - a.y
    })
  const preOrder = []
  const postOrder = []
  const split = nodes => {
    if (nodes.length === 0) {
      return
    }
    const _nodes = nodes.slice(0)
    const parentNode = _nodes.shift()
    preOrder.push(parentNode.value)
    const leftArr = nodes.filter(node => node.x < parentNode.x)
    const rightArr = nodes.filter(node => node.x > parentNode.x)
    split(leftArr)
    split(rightArr)
    postOrder.push(parentNode.value)
  }
  split(nodes)
  return [preOrder, postOrder]
}