C++로 구현하는 이분 그래프 채색(2색 칠하기) 프로그램

이분 그래프(bipartite graph)는 두 가지 색만 사용해 모든 정점을 채색할 수 있는 그래프를 말합니다. 즉, 같은 집합에 속한 정점들은 서로 동일한 색으로 칠해지며, 인접한 정점끼리는 항상 다른 색을 갖게 됩니다. 이 프로그램에서는 이분 그래프를 입력으로 받아 BFS(너비 우선 탐색) 방식으로 각 정점에 색을 입히고, 그 결과를 출력합니다.

이분 그래프의 개념

이분 그래프는 정점들을 두 개의 집합으로 나누었을 때, 모든 간선이 서로 다른 집합에 속한 정점 사이에만 존재하는 그래프입니다. 대표적인 예로 트리(tree)는 항상 이분 그래프이며, 홀수 길이의 사이클을 포함하지 않는 그래프 역시 이분 그래프입니다.

채색 알고리즘

시작
   BFS 알고리즘을 사용해 모든 정점을 순회합니다.
   한 정점을 선택해 노란색(Y)으로 칠합니다.
   해당 정점에 인접한 모든 정점을 파란색(B)으로 칠합니다.
   다음 레벨의 정점들은 노란색으로 칠하고,
   모든 정점이 칠해질 때까지 이 과정을 반복합니다.
종료

핵심 아이디어는 간단합니다. 현재 정점의 색이 결정되면, 그와 연결된 모든 이웃 정점은 반드시 반대 색이 되어야 한다는 것입니다. 색상 값은 0과 1로 관리하며, (n+1)%2 계산을 통해 매 단계마다 색을 번갈아 지정합니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<int> > g;
vector<int> color;
bool v[11101];

void c(int node, int n) {
    queue<int> q;
    if(v[node])          // 이미 방문한 정점이면 종료
        return;
    color[node] = n;     // 현재 정점에 색 지정
    v[node] = 1;         // 방문 처리
    for(i = 0; i < n; i++) {
        if(!v[g[node][i]]) {
            q.push(g[node][i]);
        }
    }
    while(!q.empty()) {
        c(q.front(), (n+1)%2);   // 이웃 정점은 반대 색으로 재귀 호출
        q.pop();
    }
    return;
}

int main() {
    int a, b;
    cout << "정점의 개수와 간선의 개수를 차례로 입력하세요:";
    cin >> n >> e;
    cout << "'Y'는 노란색(Yellow), 'B'는 파란색(Blue)을 의미합니다.";
    cout << "\n";
    g.resize(n);
    color.resize(n);
    memset(v, 0, sizeof(v));
    for(i = 0; i < e; i++) {
        cout << "\n" << i + 1 << "번째 간선의 두 정점을 입력하세요 :";
        cin >> a >> b;
        a--; b--;                 // 0 기반 인덱스로 변환
        g[a].push_back(b);        // 무방향 그래프이므로 양방향 저장
        g[b].push_back(a);
    }
    c(0, 1);                      // 0번 정점부터 노란색(1)으로 시작
    for(i = 0; i < n; i++) {
        if(color[i])
            cout << i + 1 << " " << 'Y' << "\n";
        else
            cout << i + 1 << " " << 'B' << "\n";
    }
}

실행 결과

정점의 개수와 간선의 개수를 차례로 입력하세요:4 3
'Y'는 노란색(Yellow), 'B'는 파란색(Blue)을 의미합니다.

1번째 간선의 두 정점을 입력하세요 :1 2
2번째 간선의 두 정점을 입력하세요 :3 2
3번째 간선의 두 정점을 입력하세요 :4 2
1 Y
2 B
3 B
4 B

코드 설명

그래프는 인접 리스트(vector<vector<int>) 형태로 저장되며, 무방향 그래프이므로 간선 정보를 양쪽 정점에 모두 추가합니다. 함수 c()는 재귀적으로 동작하는 BFS 변형으로, 큐에 이웃 정점을 넣어가며 색을 교대로 부여합니다. 방문 여부는 배열 v[]로 확인하여 중복 처리를 방지하고, 최종적으로 각 정점의 색 값을 검사해 'Y' 또는 'B'를 출력합니다.

이 알고리즘의 시간 복잡도는 정점의 수를 V, 간선의 수를 E라고 할 때 O(V + E)이며, 공간 복잡도 역시 O(V + E)입니다. 만약 채색 과정에서 이미 색이 칠해진 이웃 정점이 현재 정점과 같은 색이라면, 해당 그래프는 이분 그래프가 아니므로 판별 목적으로도 활용할 수 있습니다.