Node.js) 백준 11725번: 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

dfs로 풀었음.

 

class Node{
   constructor(item){
     this.item = item;
     this.next = null;
   }
 }
 
 class Queue{
   constructor(){
     this.head = null;
     this.tail = null;
     this.length = 0;
   }
 
   push(item){
     const node = new Node(item)
     if(this.head==null){
       this.head= node;
     }else{
       this.tail.next = node;
     }
     this.tail = node;
     this.length +=1;
   }
 
   pop(){
     const popItem = this.head;
     this.head = this.head.next;
     this.length -=1;
     return popItem.item;
   }
}


const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n').map(str=>str.split(' ').map(Number));

const N = input.shift()[0];
const adj = Array.from(Array(N+1),()=>[]);
const edgeTo = new Array(N+1).fill(null);
edgeTo[1] = 0
input.forEach(v=>{
   const [a,b] = v;
  adj[a].push(b);
  adj[b].push(a);
})

   let q = new Queue();
   q.push(1);  
   while(q.length>0){
      let now = q.pop();
      adj[now].forEach(v=>{
         if(edgeTo[v]==null){
            edgeTo[v] = now;
            q.push(v);
         }
      })
   }

const answer = edgeTo.slice(2,N+1).join('\n')
console.log(answer)