[boj 11724] 이분 그래프 -js

// 이분 그래프

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

const sol = (input) =>{
    const K = parseInt(input[0]);
    input = input.slice(1);

    
    
    // K개의 테스트 케이스 수행
    for(let i=0; i<K; i++){
        let [V,E] = input[0].split(' ').map(Number);
        input = input.slice(1);
        const graph = Array.from(Array(V+1),() => new Array());
        let visited = new Array(V+1).fill(0);
        
        for(let j=0; j<E;j++){ // 그래프 생성 
            const [node1,node2] = input[j].split(' ').map(Number); 
            graph[node1].push(node2);
            graph[node2].push(node1);
        }
        const dfs = (v, group) =>{ // dfs
            visited[v] = group;
            for(const node of graph[v]){
                visited[node] === 0 ? dfs(node, 3 - group) : null;
            }
        }

        for(let i=1; i<=V;i++){
            visited[i] === 0 ? dfs(i,1) : null;
        }

        let flag = true;
        out : for(let i=0; i<=V; i++){
            for(const group of graph[i]){
                if(visited[i] === visited[group]){
                    flag = false;
                    break out;
                }
            }
        }
        flag ? console.log("YES") : console.log("NO");

        input = input.slice(E);
    }
}

sol(input);

문제를 풀기 전 이분그래프가 무엇인지 정확히 파악하는 것이 중요하다! 

내가 이해한 바로는 인접한 두 노드가 같은 그룹이면 안된다는 것. 이를 구현하기 위해 그룹을 두개로 나누어 표시하였다. 

기존의 노드를 방문표시를 하였다면 이번엔 방문표시와 함께 그룹을 나타냈다. 그렇게 그룹을 나눈 뒤 이분 그래프인지 판별을 하는데 판별 방식은 그래프의 노드들의 자식 노드들과의 그룹 비교를 하면 간단하게 할 수 있다..!