[JS] 길 찾기 게임

트리구조에 대한 정확한 이해가 있어야 해결할 수 있는 문제였다.

 

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

프로그래머스

 

 

문제를 풀기 전에 가장 중점적으로 봐야할점은 2가지이다.

 

1. 한번 왼쪽으로 간 노드는 부모의 x좌표를 넘어 오른쪽으로 갈 수 없다.

2. 한번 오른쪽으로 간 노드는 부모의 x좌표를 넘어 왼쪽으로 갈 수 없다.

 

우선 JS의 sort함수를 활용하여 level을 기준으로 노드를 정렬해준 후 level별로 노드를 저장해주었다.

 

[
  [],
  [ [ 6, 1, 5 ] ],
  [ [ 2, 2, 9 ], [ 7, 2, 8 ] ],
  [ [ 1, 3, 6 ], [ 5, 3, 1 ], [ 13, 3, 3 ] ],
  [],
  [ [ 3, 5, 4 ], [ 11, 5, 2 ] ],
  [ [ 8, 6, 7 ] ]
]

 

정렬 & level 을 하면 위와 같이 트리의 노드 정보들이 배열에 담기게 된다. 

 

이제 해당 배열을 토대로 dfs로 트리를 만들어나가면서 전위,후위 탐색의 결과를 배열에 담으면 된다.

 

 

이제 방금 말했던 1,2번 조건을 생각해보자. 이 말은 dfs를 통해서 자식 노드를 만들어나갈때 자식 노드가 될 수 있는 범위가 정해져 있다는 것이다. 이를 dfs의 인자로 추가해둬서 해결하였다.

 

또한 레벨이 비어있는 경우가 있을 수 있으니 다음레벨의 배열이 비어있다면 그 다음레벨의 배열을 자식노드로 두어야 한다는 점을 꼭 생각해두자.

 

 

 

function solution(nodeinfo) {
    // [x좌표 , y좌표 , 노드번호] 로 nodeinfo를 저장
    nodeinfo = nodeinfo.map((v,idx) => [...v,idx+1])
    nodeinfo.sort((a,b) => {
        if (a[1]!==b[1]) return a[1]-b[1]
        return a[0]-b[0]
    })
    // level별로 노드 저장
    const maxLevel = nodeinfo[nodeinfo.length-1][1]
    const nodesInLevel = [...Array(maxLevel+1)].map(_ => [])
    let curLevel = 0
    for(let node of nodeinfo){
        if(node[1]!==curLevel) curLevel = node[1]
        nodesInLevel[curLevel].push(node)
    }
    
    const ret1 = []
    const ret2 = []
    
    //전위,후위 탐색
    const graph = new Map()
    const dfs = (node,left,right) => {
        const [nodeX,level,name] = node
        graph.set(name,{left:null,right:null})
        const nodeInfo = graph.get(name)
        ret1.push(node[2])
        let nxLevel = level-1
        while(nodesInLevel[nxLevel]&&!nodesInLevel[nxLevel].length) nxLevel--
        if(!nodesInLevel[nxLevel]) {
            ret2.push(node[2])
            return
        }
        for (const child of nodesInLevel[nxLevel]){
            if(!nodeInfo.left&&child[0]>left && child[0] < nodeX){
                nodeInfo.left = child[2]
                dfs(child,left,nodeX)
            }
            if(!nodeInfo.right && child[0]<right && child[0] > nodeX){
                nodeInfo.right = child[2]
                dfs(child,nodeX,right)
            }
        }
        ret2.push(node[2])
    }
    dfs(nodesInLevel[maxLevel][0],-1,Infinity)
    
    return [ret1,ret2]
}