[백준] - 1707 이분 그래프 (node.js)

문제링크

풀이

BFS로 그래프를 돌면서 1과 -1로 색깔 배열을 채우는 식으로 구현했다. 처음에 방향 그래프인줄 알고 풀었다가.. 계속 틀렸는데 😭 무방향 그래프로 수정하니 통과했다..... 하.....

코드

// 이분 그래프
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

let t = Number(input[0]);

let b = 1;
while (t) {
  let [v, e] = input[b].split(" ").map(Number);
  let graph = Array.from(new Array(v + 1), () => new Array());

  let result = true;
  for (let i = 1; i <= e; i++) {
    const [x, y] = input[i + b].split(" ").map(Number);
    graph[x].push(y);
    graph[y].push(x);
  }

  // 색칠한 인접노드 중 같은 색 노드가 있으면 이분그래프xxxx
  let color = new Array(v + 1).fill(0);

  const bfs = (i) => {
    let q = [i];
    color[i] = 1;

    while (q.length) {
      let node = q.shift();
      let nowColor = color[node];
      for (const no of graph[node]) {
        if (color[no] !== 0) { // 이미 색이 채워져 있다면
          if (color[no] === nowColor) { // 색이 지금과 같다 === 이분그래프 불가능
            result = false;
            return;
          } else continue;
        }
        q.push(no);
        color[no] = nowColor * -1;
      }
    }
  };

  for (let i = 1; i <= v; i++) {
    if (color[i] === 0) bfs(i);
  }

  console.log(result ? "YES" : "NO");
  b += e + 1;
  t--;
}