[프로그래머스]길 찾기 게임 (JS)

문제

[2019 KAKAO BLIND RECRUITMENT] 길 찾기 게임
[링크]https://programmers.co.kr/learn/courses/30/lessons/42892

문제풀이

1.트리로 만들기 위해서 좌표를 정렬한다. 우선순위는 먼저 y값이 큰 것,다음으로는 x값이 작은 것으로 구분해줬다.

• y값으로 정렬한 것은 트리의 레벨별로 정렬하고, x값이 작은 것은 왼쪽값이 먼저 나오게 하기 위함이다.

2.이 후에 재귀 함수를 돌면서 왼쪽값 먼저 들어가서 처리하고, 오른쪽 값을 들어가 처리하도록 했다.

• 전위 순회는 왼쪽값 들어가기전에 자신을 먼저 전위순회 배열에 넣어주고, 후위 순회는 왼쪽 오른쪽 처리후 자신의 값을 배열에 넣어주었다.

코드

function solution(nodeinfo) {
  //풀이 1번. 노드번호를 추가해주고, 큰 y값우선,작은 x값 우선으로 정렬.
    nodeinfo = nodeinfo.map((v,i)=>[...v,i+1]).sort((a,b)=>a[1]-b[1]===0&&a[0]-b[0]||b[1]-a[1]);
  //전위 순회,후위 순회 배열 선언;
    const pre=[];
    const post=[];
  //노드들을 왼쪽 오른쪽으로 나눠줄 재귀함수.
    function split (arr){
        if(arr.length===0)return;
        else{
          //1번 기준으로 정렬하면 맨처음 노드가 부모노드.
            const parent=arr.shift();
          //부모 노드번호를 전위순회에 등록.
            pre.push(parent[2]);
          //노드의 왼쪽 오른쪽 값을 나누어서 다시 재귀함수에 넣는다.
            const left = arr.filter((v)=>v[0]<parent[0]);//부모 노드의 x값보다 x값이 작은것들은 왼쪽 노드;
            const right = arr.filter((v)=>v[0]>parent[0]);
            split(left);
            split(right);
          //왼쪽 오른쪽 모두 처리 후 부모 노드번호를 후위순회에 등록.
            post.push(parent[2]);
        }
    }
    split(nodeinfo);
    return [pre,post];
}