[프로그래머스] 길 찾기 게임 | 자바스크립트(js) | Lv.3 | 이진트리 | 2019 KAKAO BLIND RECRUITMENT

문제

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

코딩테스트 연습 - 길 찾기 게임

 

풀이

function solution(nodeinfo) {
  const sorted = nodeinfo
    .map((el, index) => [...el, index + 1])
    .sort((a, b) => (a[1] === b[1] ? a[0] - b[0] : b[1] - a[1]));

  function order(sorted, preAnswer, postAnswer) {
    const [x, y, node] = sorted[0];
    const leftChild = [];
    const rightChild = [];

    for (let i = 1; i < sorted.length; i++) {
      const row = sorted[i];
      if (row[0] < x) leftChild.push(row);
      else rightChild.push(row);
    }

    preAnswer.push(node);
    if (leftChild.length) order(leftChild, preAnswer, postAnswer);
    if (rightChild.length) order(rightChild, preAnswer, postAnswer);
    postAnswer.push(node);
  }

  const preAnswer = [];
  const postAnswer = [];
  order(sorted, preAnswer, postAnswer);
  return [preAnswer, postAnswer];
}

이 문제는 각 노드마다 x와 y좌표가 주어진다. 이진트리이기 때문에 자식 노드는 최대 2개만 가질 수 있다. 처음에는 무작정 Y값이 현재 노드보다 작은 것을 탐색하고 그 중 X값이 작으면 왼쪽에 배치, X값이 크면 오른쪽에 배치 하려고 했으나..! 그렇게 하면 아래 그림에서 예외가 발생한다.
2노드의 왼쪽 아래에 1이 존재하지만, 1은 2의 자식노드는 아니다. 따라서 단순히 x, y좌표로만 판단해서는 안된다..

const sorted = nodeinfo
  .map((el, index) => [...el, index + 1])
  .sort((a, b) => (a[1] === b[1] ? a[0] - b[0] : b[1] - a[1]));

먼저 y를 기준으로 정렬을 해줘야 한다. 그 전에 해당 노드의 인덱스를 기억할 필요가 있으므로 마지막 원소에 index를 추가해준다. 왼쪽부터 탐색할 것이기 때문에 y값이 같다면 x값을 기준으로 오름차순으로 정렬해준다.

이제 순회 함수를 보자.

function order(sorted, preAnswer, postAnswer) {
   const [x, y, node] = sorted[0];
   const leftChild = [];
   const rightChild = [];

   for (let i = 1; i < sorted.length; i++) {
      const row = sorted[i];
      if (row[0] < x) leftChild.push(row);
      else rightChild.push(row);
   }

   preAnswer.push(node);
   if (leftChild.length) order(leftChild, preAnswer, postAnswer);
   if (rightChild.length) order(rightChild, preAnswer, postAnswer);
   postAnswer.push(node)
}

sorted의 상위노드를 꺼내준다. 해당 상위 노드는 answer에 하나씩 push할 node이다.
순회를 시작하기 전에 answer에 push하면 전위순회, 순휘가 끝난 후 뒤에서부터 push하면 후위순회가 된다.

여기서 주목해야 할 것은 반복문의 i는 1부터 시작한다는 것이다. 이미 정렬이 돼있는 배열이므로, 상위노드의 아래 노드들을 쭉 탐색한다.
상위노드의 x값보다 작다면 왼쪽 서브 트리를 구성하는 노드이므로 leftChild에 넣어주고, 상위노드의 x값보다 크다면 오른쪽 서브트리를 구성하는 노드이므로 rightChild에 넣어준다.

preAnswer에는 상위노드를 순차적으로 저장하면 되고, 왼쪽 자식과 오른쪽 자식이 있을 경우, 각각 왼쪽 순회와 오른쪽 순회를 돌게 된다. 만약 왼쪽 자식(leftChild)과 오른쪽 자식(rightChild)이 모두 없다면 순회는 끝났다. 이제 맨 하단의 노드부터 재귀를 끝내면서 postAnswer에 저장될 것이다.

사실 트리를 어떻게 배열로 구성해야 할까 엄청 많은 고민을 했다. 그럴 필요없이 정렬을 하면 되는데 대신 인덱스를 기억해야 한다는 사실까지 스스로 알아낼 수 있지만..! 순회를 까먹어서 다시 공부하면서 구현했다