자바스크립트 코딩테스트 강좌, 이분 그래프 판별하기

코딩테스트에서 그래프 문제는 자주 출제됩니다. 이 분 그래프란 두 개의 집합으로 나눌 수 있는 그래프를 의미하며, 인접한 두 정점이 서로 다른 집합에 속하도록 할 수 있는지를 판별하는 문제입니다. 이번 강좌에서는 이분 그래프를 판별하는 알고리즘에 대해 알아보겠습니다.

문제 정의

주어진 무방향 그래프가 이분 그래프인지 판별하는 함수를 작성하세요. 이분 그래프는 정점들을 두 개의 그룹으로 나누어, 같은 그룹에 있는 두 정점 간에 간선이 존재하지 않아야 합니다.

입력

정점의 수 n (1 ≤ n ≤ 1000)
간선의 수 m (0 ≤ m ≤ 1000)
m개의 간선 정보 (정수 쌍 u, v로, 정점 u와 정점 v가 연결되어 있음을 의미합니다)

출력

이 그래프가 이분 그래프이면 true, 아니면 false를 출력하세요.

문제 접근 방법

이분 그래프를 판별하기 위해서는 그래프를 색칠하는 기법을 사용할 수 있습니다. 각 정점을 두 가지 색, 예를 들어 ‘0’과 ‘1’로 색칠하여 인접한 정점이 같은 색으로 색칠되면 이분 그래프가 아니라는 것입니다.

구현 방법은 다음과 같습니다:

그래프를 인접 리스트 형태로 표현
각 정점의 색을 저장할 배열을 생성
너비 우선 탐색(BFS) 또는 깊이 우선 탐색(DFS)을 사용하여 정점을 방문하고 색칠하기
인접 정점의 색이 같은 경우, 이분 그래프가 아님을 반환

코드 구현

자바스크립트를 사용하여 위 단계에 따라 이분 그래프를 판별하는 함수를 구현해보겠습니다.


function isBipartiteGraph(n, edges) {
    // 그래프를 인접 리스트로 표현
    const graph = Array.from({length: n}, () => []);
    edges.forEach(([u, v]) => {
        graph[u].push(v);
        graph[v].push(u); // 무방향 그래프이므로 양쪽에 추가
    });

    const colors = Array(n).fill(-1); // 각 정점의 색을 저장 (-1: 미방문, 0: 첫 번째 색, 1: 두 번째 색)

    const bfs = (start) => {
        const queue = [start];
        colors[start] = 0; // 시작 정점은 첫 번째 색으로 색칠

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

            for (const neighbor of graph[node]) {
                if (colors[neighbor] === -1) {
                    // 인접 정점이 미방문이면 색칠하고 큐에 추가
                    colors[neighbor] = 1 - colors[node];
                    queue.push(neighbor);
                } else if (colors[neighbor] === colors[node]) {
                    // 인접 정점의 색이 현재 노드와 같으면 이분 그래프가 아님
                    return false;
                }
            }
        }
        return true;
    };

    // 모든 정점을 확인하여 연결된 컴포넌트가 있을 경우 BFS 수행
    for (let i = 0; i < n; i++) {
        if (colors[i] === -1) {
            if (!bfs(i)) return false;
        }
    }
    
    return true;
}

// 테스트 케이스
const n = 4;
const edges = [[0, 1], [0, 2], [1, 3], [2, 3]];
console.log(isBipartiteGraph(n, edges)); // false

알고리즘 분석

위의 알고리즘은 너비 우선 탐색(BFS)을 사용하여 그래프의 모든 정점을 탐색합니다. 그에 따라 시간 복잡도는 O(n + m)입니다. 여기서 n은 정점의 수, m은 간선의 수입니다. 이는 그래프의 모든 정점과 간선을 한 번씩 탐색하기 때문입니다.

공간 복잡도 또한 O(n + m)으로 인접 리스트와 색 배열을 저장하기 위해 이 정도의 공간이 필요합니다.

결론

이번 강좌에서는 이분 그래프를 판별하는 알고리즘에 대해 알아보았습니다. 이 알고리즘을 통해 그래프 문제를 해결할 때 이분 그래프인지 여부를 판단할 수 있습니다. 이 알고리즘은 다양한 문제에 활용될 수 있으므로 확실히 이해해 두면 좋습니다.

또한, 이 문제의 해결 방법은 BFS 외에도 DFS를 사용하여도 유사하게 구현할 수 있습니다. 알고리즘의 고유 특성을 이해하고 이를 바탕으로 다양한 변형 문제를 풀어보세요.

추가 연습 문제

이해를 돕기 위해 다음의 문제를 풀어보세요:

대칭 적 이분 그래프 판별: 주어진 간선 정보가 대칭적으로 주어지는 경우에 대해 이분 그래프 여부를 판단하라.
이분 그래프의 최대 매칭: 주어진 이분 그래프에서 최대 매칭을 찾는 알고리즘을 구현하라.

참고 자료

이분 그래프에 관한 자세한 설명은 Wikipedia의 이분 그래프 문서를 참고하시기 바랍니다.