[Refresh ! 코딩 테스트 / js] - 310. Minimum Height Trees

문제 해석

• dfs 으로 높이 노드를 찾는게 아니다.
• 주어진 그래프는 양방향 그래프로 . 최소한의 길이를 가지고 있는 root 노드를 찾으시오
• example 1 를 보면 0 이 root 노드라고 가정했을때 높이는 2 이지만. 1 이 root 노드라고 가정했을때 높이는 1 임으로 정답은 [1] 이다.

나의 풀이

❌ Solution

• 막연히 그냥 for 문으로 한번씩 돌리면서 root 노드를 가정하고 높이를 측정해서 return 하면 되는구나 싶었다.
• 당연히 시간 복잡도는 엉망 + 정답이 아니였다.

var findMinHeightTrees = function(n, edges) {
    //root 노드를 찾는 간단한 문제

    obj={};
    edges.forEach((El)=>{
        let [start,end]=El
        if(!obj[start]) obj[start]=[end];
          else {
            obj[start].push(end);
        }
        if(!obj[end]) obj[end]=[start];
        else{
             obj[end].push(start);
        }
      
     })
     // 이거를 토대로 bfs 깊이 우선 돌리면서 가면 됨

     const dfs= function(start_node,visited_arr){
       let final_length=Infinity;
       let queue=[[start_node,0]];
       while(queue.length>0){
         let [first_go,count]= queue.shift();
         // 하나빼기 
         if(visited_arr[first_go]==0){
            // 이런경우에만 갈수 있음
            visited_arr[first_go]=1;
            for(var i=0; i<obj[first_go].length; i++){
                let what_is_go= obj[first_go][i]
                if(visited_arr[what_is_go]==0){
                    visited_arr[what_is_go]=1;
                    // 하나갈수 있다고 가정하고 
                    queue.unshift([what_is_go,count+1])
                    final_length= Math.min(final_length,count+1)
                }
            }
         }
       }
      return final_length;
     }
     let real_answer=Infinity;
     for(var i=0;i<n; i++){
        //시작하는 노드
          let visited=Array.from({length:n}).fill(0);
        real_answer= Math.min(dfs(i, visited),real_answer)
     }

 return real_answer;



};

✅ Solution( 100 / 100 )

• 양방향 노드에 집중해서 obj 형태로 만든것을 set 형태로 바꿨다.
• 따라서 if 문으로 obj 을 확인하면서 만들필요 xxx
• 자식노드가 없는 노드는 == > 지우기
• 자식 노드가 없는 노드의 부모가 이번에 자식노드가 없어지면 그 부모도 지우기
• 를 반복하면서 결국에는 맨 root 을 찾는 개념이라고 생각하면 된다.
• 이때 부모노드에 포함되어있던 "필요없는 자식노드" 를 delete 으로 삭제시키기 위해 set 을 사용했다고 생각
• set 은 index 으로 pick 할수 없으니 [..] 형식으로 바꿔서 부모 노드를 찾아냈다.

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var findMinHeightTrees = function(n, edges) {
    //root 노드를 찾는게 아니라 양방향으로 연결된 tree 중 깊이가 최소 인것을 찾는문제 
     if(n==1) return [0]
    let new_tree= Array.from({length:n},()=>new Set());
    edges.forEach((el)=>{
        let [a,b]=el;
        new_tree[a].add(b);
        new_tree[b].add(a);
    })
    let go_queue=[]
   // 가운데 있는 루트를 찾기 위해서 자식노드가 없는 leaf 을 찾아야된다
   new_tree.forEach((EO,index)=>{
    if(new_tree[index].size==1){
       go_queue.push(index)
    }
   })
   // leaf 노드( 시작점을 알아냄)
   let total_node_length= n;
   while(total_node_length>2){
    //여기서 leaf 노드를 삭제해야됨 따라서 leaf 노드를 삭제한 부모의 자식도 없어지면. 다시 넣어서 while 문을 돌린다는 의미
    // go_queue 에다가 bfs 을 한다는 의미라고 생각해도됨
    total_node_length-=go_queue.length;

     let hey_check=[]
    for(const hey of go_queue){
        let check= [...new_tree[hey]][0];
         //set의 인덱스에 접근할수 없다
        new_tree[check].delete(hey);
        // 자식노드를 지운다.
        if(new_tree[check].size==1){
         hey_check.push(check)
        }
    }
      go_queue=hey_check;
   }
   return go_queue




};