[JS] 백준 1707 : 이분그래프 - 그래프이론, BFS, 이분그래프

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

1707번: 이분 그래프

 

 

이분 그래프(Bipartite Graph)란
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.

즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는(<=> 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프라고 한다.

 

 

풀이방법

1. 테스트 케이스마다 다른 그래프가 형성된다.

2. u -> v 와 v -> u의 정보를 저장하는 graph배열을 선언한다.

3. 1 ~ V 를 인덱스로 하고 색상의 정보를 저장하는 visited배열을 선언한다.

 - 즉 arr[1]부터 값을 1 또는 2 라는 색상으로 저장할 것 이다.

 - 초기에는 0으로 초기화돼서 이후 디폴트색상인 1로 칠해진다.

4. 주어진 V 정점들을 모두 순회하면서 visited값이 0이면 BFS를 실행한다.

5. BFS

6. BFS이므로 queue에 정점을 넣어준다.

7. check라는 변수를 1로 초기화한다 -> 디폴트 색상

8. visited에 해당 정점을 1로 칠해준다.

9. while문에서 큐가 빌 때까지 반복한다.

10. 만약 현재 visited값이 1이면 check를 2로, 2면 check를 1로 지정한다.

 ->이는 현재 정점과 연결되는 다른 정점은 현재 정점의 색상과 무조건 반대되는 색상이여야한다.

11. 현재 정점에서 연결된 간선의 정보를 저장한 graph배열을 이용해 연결된 정점을 순회한다.

12. 만약 연결된 정점이 아직 색칠이 칠해지지않은 0이라면 반대되는 색상 check로 지정해주고, 그 정점을 queue에 넣는다.

 ->queue에 넣어서 BFS로 뻗어나가는 것이다.

 ->먼저 현재 정점과 연결된 모든 정점을 반대되는 색상으로 칠해준 뒤에 차례대로 검사하는 것이다.

13. 만약 이후 현재 정점의 색상과 연결된 정점의 색상이 같을 때 BFS를 종료해준다.

  -> 색상이 같다면 이후 이분 그래프임을 검사할 때 증명될 것이다.

14. 이분그래프 증명 isAns함수

15. 현재 정점에서 연결된 정점의 정보를 저장한 graph배열을 순회한다.

16. i는 현재 정점 next에는 연결된 정점을 저장한다.

17. 만약 i의 색상과 next의 색상이 같은 상황이 생기면 반복을 종료하고 No를 출력한다.

18.만약 반복이 종료가 안된다면 Yes를 출력한다.

 

 

🤟내 제출

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

let K = Number(input[0]);
let n = 1;
let arr = Array.from({ length: K }, () => Array());
for (let i = 0; i < K; i++) {
  let [V, E] = input[n].split(" ").map(Number);
  arr[i].push([V, E]);
  for (let j = 0; j < E; j++) {
    arr[i].push(input[n + 1 + j].split(" ").map(Number));
  }
  n += E + 1;
}

for (let k = 0; k < arr.length; k++) {
  let [V, E] = arr[k][0];
  //그래프 정보 (u - v)
  const graph = Array.from({ length: V + 1 }, () => []);
  //간선의 배열 (1 ~ V)
  const visited = Array.from({ length: V + 1 }, () => 0);

  for (let i = 1; i <= E; i++) {
    const [from, to] = arr[k][i];
    graph[from].push(to);
    graph[to].push(from);
  }
  const bfs = (start) => {
    let queue = [start];
    let check = 1;
    //처음에는 1로 색상을 정해줌
    visited[start] = check;

    while (queue.length) {
      let cur = queue.shift();
      //만약 cur에 1로 칠해져있으면 2로 체크한다. 반대로 2로 칠해져있으면 1로 체크한다.
      // ->체크하는 이유는 두 정점은 다른 색상, 즉 다른 숫자여야하므로
      if (visited[cur] === 1) check = 2;
      else if (visited[cur] === 2) check = 1;

      //정점 cur에 이어진 간선을 순회
      for (let i = 0; i < graph[cur].length; i++) {
        //next : cur에 이어진 정점
        let next = graph[cur][i];
        //해당 정점이 0이면 (색상이 정해지지않은 것)
        if (!visited[next]) {
          //cur과 반대되는 색상으로 칠해준다.
          visited[next] = check;
          //그리고 그 간선의 도착 정점을 queue에 넣어서 그 정점도 확인한다.
          queue.push(next);
        } else if (visited[cur] === visited[next]) {
          //만약 도착 정점의 색상이 cur의 색상과 같다면 이분그래프가 아님 (연결된 정점은 무조건 색상이 달라야 이분그래프임)

          return;
        }
      }
    }
  };
  //간선의 배열에 꼭짓점을 1 또는 2로 정함 -> 0이라면 BFS를 시작함
  //visited는 1 또는 2로 정해짐
  for (let i = 1; i <= V; i++) {
    //중요한 점은 모든 정점을 무조건 순회하면서 간선이 없더라도 bfs에서 기본적으로 1이라는 색상으로 칠해줌
    if (!visited[i]) {
      bfs(i);
    }
  }
  console.log(visited);
  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();
}

 

 

💢어려웠던 점

1. 이분그래프라는 것을 잘 몰랐다.

 -처음에는 그저 연결이 안된 정점을 찾는 건가 했다.

 -연결된 정점의 색상이 무조건 달라야하는 것이 이분그래프이다.