[백준] 1707 이분 그래프 - javascript

📌 문제

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

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

let tc = +input.shift();
let index = 0;
while (tc--) {
  const [V, E] = input[index++].split(' ').map(Number);
  const graph = Array.from({ length: V + 1 }, () => []);
  const visited = Array.from({ length: V + 1 }, () => 0);

  for (let i = 0; i < E; i++) {
    const [from, to] = input[index + i].split(' ').map(Number);
    graph[from].push(to);
    graph[to].push(from);
  }
  const bfs = (start) => {
    let queue = [start];
    let check = 1;

    visited[start] = check;

    while (queue.length) {
      let cur = queue.shift();

      if (visited[cur] === 1) check = 2;
      else if (visited[cur] === 2) check = 1;

      for (let i = 0; i < graph[cur].length; i++) {
        let next = graph[cur][i];
        if (!visited[next]) {
          visited[next] = check;
          queue.push(next);
        } else if (visited[cur] === visited[next]) {
          return;
        }
      }
    }
  };

  for (let i = 1; i <= V; i++) {
    if (!visited[i]) {
      bfs(i);
    }
  }

  const isAns = () => {
    for (let i = 1; i <= V; i++) {
      for (let j = 0; j < graph[i].length; j++) {
        let next = graph[i][j];
        if (visited[i] === visited[next]) {
          return console.log('NO');
        }
      }
    }
    return console.log('YES');
  };
  isAns();
  index += E;
}

✔ 알고리즘 : BFS

✔ ❓ 이분 그래프란
2가지 색으로 꼭짓점을 칠할 때 모든 변의 두 꼭짓점의 색깔이 달라야 이분 그래프이다.

✔ visited 배열을 통해 현재 색깔이 칠해져있는지 (1,2) 아니면 색이 안칠해져있는지(0) 판단

✔ BFS 탐색을 하며 queue에서 방금 뽑은 색깔과 반대색으로 현재 꼭짓점을 칠한다.

let cur = queue.shift();

if (visited[cur] === 1) check = 2;
else if (visited[cur] === 2) check = 1;

✔ 하나의 edge라도 두 꼭짓점이 같은 색깔인 경우 이분그래프가 아니다.

const isAns = () => {
  for (let i = 1; i <= V; i++) {
    for (let j = 0; j < graph[i].length; j++) {
      let next = graph[i][j];
      if (visited[i] === visited[next]) {
        return console.log('NO');
      }
    }
  }
  return console.log('YES');
};

❗ 그래프를 입력받는 부분인

const [from, to] = input[index + i].split(' ').map(Number);

에서 index로 접근하지 않고 input.shift()로 접근을 했을 때는 시간초과가 발생하였다. 따라서 꽤 데이터의 양이 많을 때는 input.shift() 메서드 보다는 index를 통해서 input 데이터에 접근하는 것이 좋을 것 같다.

✔ 난이도 : 백준 기준 골드 4