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

1. 서론

그래프 이론은 컴퓨터 과학과 알고리즘의 중요한 분야로, 다양한 실제 문제를 해결하는 데 활용됩니다.
이 글에서는 ‘이분 그래프’의 개념과 이를 판별하는 알고리즘 문제를 소개하고, C#으로 이를 해결하는 방법을
자세히 설명하겠습니다. 이분 그래프란 그래프의 정점을 두 개의 집합으로 나눈 후, 같은 집합의 정점끼리는
연결되지 않도록 만들어진 그래프를 말합니다. 이러한 그래프는 여러 가지 응용 분야에서 중요한 역할을 합니다.
예를 들어, 두 종류의 객체 간의 연결 관계나 이분 매칭 문제 등에서 자주 사용됩니다.

2. 문제 설명

이 문제에서는 그래프가 주어졌을 때, 이분 그래프인지 아닌지를 판별하는 알고리즘을 구현해야 합니다.
예를 들어, 그래프의 정점 수 V와 간선 수 E가 주어지고, V개의 정점과
E개의 간선이 이어져 있습니다. 주어진 그래프가 이분 그래프일 경우에는 “YES”를 출력하고, 그렇지 않을 경우에는
“NO”를 출력해야 합니다.

입력 형식

        첫 번째 줄에는 정점의 수 V와 간선의 수 E가 주어진다.
        다음 E개의 줄에는 간선의 양 끝 점을 나타내는 두 정수가 주어진다.

출력 형식

        주어진 그래프가 이분 그래프일 경우 "YES", 그렇지 않을 경우 "NO"를 출력한다.

3. 알고리즘 접근 방식

이 문제를 해결하기 위해, 우리가 사용할 알고리즘은 BFS (너비 우선 탐색) 또는 DFS (깊이 우선 탐색)입니다.
이분 그래프 판별을 위해 각 정점을 두 개의 색으로 칠하는 방법을 사용할 것입니다.
즉, 하나의 집합은 색상 1로 표시하고 다른 집합은 색상 2로 표시합니다. 만약 인접한 두 정점이 동일한 색상으로
칠해진다면 이분 그래프가 아니라는 것을 의미합니다.

알고리즘 단계

그래프를 인접 리스트 형식으로 나타내기 위해 데이터 구조를 생성합니다.
BFS 또는 DFS를 사용하여 정점을 방문하며, 정점의 색상을 결정합니다.
인접한 정점이 동일한 색상인지 체크하여 이분 그래프 여부를 판단합니다.
모든 정점을 방문하고 나서 최종 결과를 출력합니다.

4. C# 코드 구현

이제 앞서 설명한 알고리즘을 바탕으로 C#으로 코드를 구현하겠습니다.
아래는 이분 그래프 판별을 위한 C# 코드입니다.

using System;
using System.Collections.Generic;

class Program
{
    static List[] graph;
    static int[] color;

    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int V = int.Parse(input[0]);
        int E = int.Parse(input[1]);

        graph = new List[V + 1];
        for (int i = 0; i <= V; i++)
            graph[i] = new List();

        for (int i = 0; i < E; i++)
        {
            input = Console.ReadLine().Split();
            int u = int.Parse(input[0]);
            int v = int.Parse(input[1]);
            graph[u].Add(v);
            graph[v].Add(u);
        }

        color = new int[V + 1];

        bool isBipartite = true;
        for (int i = 1; i <= V; i++)
        {
            if (color[i] == 0)
                isBipartite &= BFS(i);
        }

        Console.WriteLine(isBipartite ? "YES" : "NO");
    }

    static bool BFS(int start)
    {
        Queue queue = new Queue();
        queue.Enqueue(start);
        color[start] = 1;  // 최초 정점 색칠

        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            foreach (int neighbor in graph[node])
            {
                if (color[neighbor] == 0)  // 아직 색칠 안 된 경우
                {
                    color[neighbor] = 3 - color[node];  // 현재 정점과 다른 색
                    queue.Enqueue(neighbor);
                }
                else if (color[neighbor] == color[node])  // 인접한 두 정점 색이 같으면
                {
                    return false;
                }
            }
        }
        return true;
    }
}

5. 코드 설명

위 C# 코드에서 사용된 주요 구성 요소와 로직을 설명하겠습니다.

자료구조

– List[] graph: 그래프를 인접 리스트로 표현하기 위해 사용됩니다.
정점 번호를 키로 하여 연결된 정점 리스트를 저장합니다.

– int[] color: 각 정점의 색을 저장합니다. 0은 색칠 안 된 상태, 1과 2는 각각의 색을 나타냅니다.

메인 메서드

– 입력으로 그래프의 정점 수와 간선 수를 받고, 이를 기반으로 그래프를 생성합니다.

– 모든 정점을 순회하며, BFS를 호출하여 이분 그래프 여부를 확인합니다.
주어진 모든 정점에 대해 확인 후 결과를 출력합니다.

DFS 메서드

– BFS 메서드는 큐를 기반으로 너비 우선 탐색을 수행합니다.
시작 정점을 색칠하고, 인접한 정점이 색칠되지 않았다면 현재 정점과 다른 색으로 색칠합니다.

– 이미 색칠된 정점이 현재 정점과 같은 색으로 색칠되어 있다면 이분 그래프가 아니므로 false를 반환합니다.

6. 복잡도 분석

본 알고리즘의 시간복잡도는 O(V + E)입니다.
V는 정점의 수, E는 간선의 수이며, 그래프의 모든 정점과 간선을 탐색하기 때문입니다.
따라서 주어진 입력 크기에 대해 효율적으로 작동할 수 있습니다.

7. 결론

이 글에서는 이분 그래프의 정의와 이를 판별하는 문제를 C#으로 해결하는 방법에 대해 설명했습니다.
그래프 이론의 기초와 BFS/DFS 알고리즘을 익히고, 이를 실전에 활용하는 데 도움이 되었기를 바랍니다.
또한, 다양한 문제를 풀어보며 그래프 알고리즘에 대한 이해를 높여가길 바랍니다.