Node.js) 백준 1707 : 이분 그래프 (시간초과 해결방법)

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

1707번: 이분 그래프

시간 초과 해결방법: readline 모듈 + 입력값을 모두 큐에 넣어주기.

 

입력값이 많을 때는 readLine  모듈과 큐를 함께 사용해서 구현 

 

 

 

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;
      this.head.next = null;
    }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;
  }
  
  size(){
    return this.length;
  }
  
  empty(){
    if(this.length==0){
      return 1;
    }else{
      return 0;
    }
  }
  
  front(){
    if(this.empty()==1) return -1;
    return this.head.item; 
  }
  
  back(){
    if(this.empty()==1) return -1;
    return this.tail.item; 
  }
}

function solve(N,graphInfo) {
  let answer = [];
  for(let i = 0; i<N; i++){
    let [V,E] = graphInfo.pop().split(' ').map(v=>+v);
    let isVisited = new Array(V+1).fill(null);
    let adj = [];
    for(let j = 0; j<=V; j++){
      adj.push(new Queue());
    }
    for(let k = 0; k<E; k++){
      let [u,v] = graphInfo.pop().split(' ').map(v=>+v);
      adj[u].push(v);
      adj[v].push(u);
    }
    let l = 1;
    let tempAnswer = 'YES'
    while(l<=V && tempAnswer=='YES'){
    if(isVisited[l]==null){
      let q = new Queue();
      isVisited[l] = true;
      q.push(l);
      while(!q.empty()&&tempAnswer=='YES'){
        
        let now = q.pop();
        let type = isVisited[now];
        let arr = adj[now];
        while(!arr.empty()){
          let temp = arr.pop();
          if(isVisited[temp]==type){
            tempAnswer = 'NO'
            break;
          }else if(isVisited[temp]==null){
            isVisited[temp]=!type;
            q.push(temp)
          }
        }
      }
    }
    l++;
    }
    answer.push(tempAnswer)
  }
  
  console.log(answer.join('\n'))

}

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = new Queue();
rl.on("line", function(line) {
  input.push(line)
}).on("close", function() {
  let n = +input.pop();
  solve(n, input);
  process.exit();
});