C++ 코딩테스트 강좌, 이분 그래프 판별하기

안녕하세요! 오늘은 이분 그래프에 대해서 알아보겠습니다. 이분 그래프는 그래프의 정점 집합을 두 개의 부분 집합으로 나눌 수 있으며, 두 집합에 포함된 정점 간에는 간선이 존재하지 않는 그래프를 의미합니다. 이 내용은 코딩테스트에서 자주 출제되는 문제 중 하나입니다. 다음 시간에는 이 문제를 풀기 위해 필요한 알고리즘과 코딩을 통해 이분 그래프를 판별하는 방법에 대해 알아보겠습니다.

문제 설명

주어진 비방향 그래프가 이분 그래프인지 판별하는 문제입니다. 한 정점에서 시작하여, 가능한 모든 정점을 방문하면서 이분 그래프 조건을 만족하는지를 확인해야 합니다.

문제 예제

다음과 같은 그래프가 주어졌을 때, 이 그래프가 이분 그래프인지 판별하시오.

정점: 6
간선: 
1 - 2
1 - 3
2 - 4
2 - 5
3 - 6

위 그래프를 보면 두 개의 집합으로 나눌 수 있는지 파악할 수 있습니다. 집합 A는 {1, 4, 5, 6}이고, 집합 B는 {2, 3}입니다. 이 그래프는 이분 그래프가 맞습니다.

문제 해결 전략

이분 그래프를 확인하기 위해 우리가 사용할 수 있는 방법 중 하나는 너비 우선 탐색(BFS) 혹은 깊이 우선 탐색(DFS)입니다. 두 방법 모두 그래프를 순회할 때 각 정점에 색깔(또는 그룹)을 부여하여 이분 그래프 조건을 확인하는 데 사용할 수 있습니다.

알고리즘 단계

1. 그래프를 인접 리스트 형태로 표현합니다.
2. 모든 노드를 방문할 수 있도록 반복문을 실행합니다.
3. 현재 정점에 색칠을 하여 두 그룹으로 나눕니다.
4. 인접한 정점이 같은 색깔인지 확인합니다.
5. 모든 노드를 방문하였거나 갈 수 있는 노드를 모두 방문할 때까지 반복합니다.

C++ 코드 구현

이 비방향 그래프에서 이분 그래프를 판별하기 위한 C++ 코드를 살펴보겠습니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 1000; // 정점의 최대 개수
vector<int> graph[MAX];
int color[MAX]; // 색상 설정: -1은 미방문, 0과 1은 그룹

bool isBipartite(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 0; // 시작 정점에 색칠

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int neighbor : graph[v]) {
            // 이웃 정점이 방문하지 않았다면 색칠한다.
            if (color[neighbor] == -1) {
                color[neighbor] = 1 - color[v]; // 현재 정점과 다른 색상을 부여
                q.push(neighbor);
            }
            // 이웃 정점이 현재 정점과 같은 색이라면 이분 그래프가 아니다.
            else if (color[neighbor] == color[v]) {
                return false; // 이분 그래프 조건 위배
            }
        }
    }
    return true;
}

int main() {
    int v, e;
    cout << "정점의 개수와 간선의 개수를 입력하세요: ";
    cin >> v >> e;

    // 그래프 초기화
    for (int i = 0; i < MAX; i++) {
        color[i] = -1;
    }

    cout << "간선 입력 (형식: a b): " << endl;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a); // 양방향 그래프
    }

    bool result = true;
    for (int i = 1; i <= v; i++) {
        if (color[i] == -1) {
            // 이 정점이 미방문 상태라면 이분 그래프 판별
            if (!isBipartite(i)) {
                result = false;
                break;
            }
        }
    }

    if (result) {
        cout << "이 그래프는 이분 그래프입니다." << endl;
    } else {
        cout << "이 그래프는 이분 그래프가 아닙니다." << endl;
    }

    return 0;
}

코드 설명

이 코드는 주어진 그래프의 정점과 간선을 입력받아 그 그래프가 이분 그래프인지 판단하는 과정입니다. isBipartite 함수는 모든 인접한 정점이 다른 색상으로 되어 있는지 검사합니다.

변수 및 구조체 설명

• graph[MAX]: 그래프의 인접 리스트 표현입니다.
• color[MAX]: 정점의 색상을 나타내는 배열입니다.
• queue<int> q: BFS에 사용되는 큐입니다.

입력 예시 및 출력 결과

위 코드를 실행할 때 간선을 입력하는 예시는 다음과 같습니다.

정점의 개수와 간선의 개수를 입력하세요: 6 5
간선 입력 (형식: a b): 
1 2
1 3
2 4
2 5
3 6

위와 같은 입력을 주었을 때, 아래와 같은 결과를 출력합니다.

이 그래프는 이분 그래프입니다.

결론

이상으로, C++를 이용하여 이분 그래프를 판별하는 방법을 배웠습니다. BFS 또는 DFS 방식을 사용하여 문제를 해결하는 기본적인 원리를 이해했다면, 이는 다양한 그래프 문제에 적용될 수 있습니다. 여러분의 코딩테스트 준비에 많은 도움이 되기를 바랍니다!