백준 1707번 이분 그래프 JavaScript 풀이 [BFS]

백준 1707번 이분 그래프 문제를 자바스크립트로 BFS 알고리즘을 이용해서 풀어보았다. 

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

 

while 문으로 BFS 돌리기 전에 모든 노드를 순회하는 for문을 추가해줬어야 했다.

이것 때문에 한참 헤맸다..

/* 
'/dev/stdin'
*/
let path = 'input.txt';

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let testCase = Number(input[0]);
let t = 1;

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }
  getLength() {
    return this.tail - this.head;
  }
}

while (testCase--) {
  let [v, e] = input[t].split(' ').map(Number);
  let graph = new Array(v+1).fill().map(_ => []);
  for (let i=1; i<=e; i++) {
    let [start, end] = input[t + i].split(' ').map(Number);
    graph[start].push(end);
    graph[end].push(start);
  }

  // 미방문 0, 검정색 : 1, 하얀색 : -1
  let visited = new Array(v+1).fill(0);

  // 모든 노드 순회
  for (let node=1; node<=v; node++) {
    // 방문 안한 노드이면
    if (visited[node] == 0) {
      queue = new Queue();
      queue.enqueue(node)
      visited[node] = 1;

      // BFS로 색상값을 visited에 삽입
      while (queue.getLength() != 0) {  
        let x = queue.dequeue(); 
        for (let y of graph[x]) {
          if (visited[y] == 0) {
            visited[y] = visited[x] * (-1);
            queue.enqueue(y);
          }
        }
      }
    }
  }

  // 이분 그래프인지 visited를 순회하면서 확인
  let result = "YES";
  for (let x=1; x<=v; x++) {
    for (let y of graph[x]) {
      if (visited[x] == visited[y]) {
        result = "NO";
        break;
      }
    }
  }
  console.log(result)
  
  // 다음 테스트 케이스로 이동  
  t += e + 1;
}