[JS] 백준 1707번 이분 그래프

---

문제 링크

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

풀이 전략

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html
우선 이분그래프에 대해서 자세히 알 필요가 있다.
이 블로그에 잘 정리해주신 분이 계셔서 상대적으로 쉽게 개념을 이해할 수 있었다. 
다시 설명해보자면, 그래프가 존재하는데 이 그래프를 둘로 나누었을 때 모든 정점이 간선으로 연결되어있으면 이분그래프이다.
즉, 같은 그룹에 속한 정점은 인접하지 않아야한다.  

코드 

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

const k = +input.shift();
const ORIGIN = 1;
const ANOTHER = -1;
let idx = 0;

solution(input.map((v) => v.split(" ").map(Number)));

function solution(arr) {
    const answerArr = [];

    for (let i = 0; i < k; i++) {
        const [v, e] = arr[idx++];
        const colorArr = Array.from({ length: v + 1 }, () => 0);
        const list = Array.from({ length: v + 1 }, () => []);
        let flag = 1;

        for (let i = 0; i < e; i++) {
            const [u, v] = arr[idx++];

            list[u].push(v);
            list[v].push(u);
        }

        for (let i = 1; i <= v; i++) {
            if (colorArr[i] === 0) {
                colorArr[i] = ORIGIN;
                if (bfs(i)) {
                    flag = 0;
                    break;
                }
            }
        }

        if (flag) answerArr.push("YES");
        else answerArr.push("NO");

        function bfs(start) {
            const queue = [];
            colorArr[start] = ORIGIN;
            queue.push(start);

            while (queue.length) {
                const v = queue.shift();

                for (let i = 0; i < list[v].length; i++) {
                    const nv = list[v][i];
                    if (colorArr[nv] === 0) {
                        colorArr[nv] = colorArr[v] * ANOTHER;
                        queue.push(nv);
                    } else if (colorArr[nv] === colorArr[v]) {
                        return true;
                    }
                }
            }
            return false;
        }
    }

    console.log(answerArr.join("\n"));
}

 

회고

https://www.acmicpc.net/board/view/82647

처음 시도하였을 때, 50%에서 오답이 나왔다. 이유를 검색해보니 List배열에 적힌 간선들이 모두 연결되어있다는 보장이 없기 때문에 이를 체크하기 위해서 1 ~ V까지 모든 노드를 탐색해주어야한다. 이를 위해 flag변수를 선언하고 flag가 참이면 YES 아니면 NO를 배열에 넣어주었다. ColorArr와 List를 bfs함수 안에 매개변수로 넣으면 메모리가 많이 소모될 것 같아 for문안으로 넣어주었는데, 별로 마음에 들지 않는 코드 스타일이다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)