[PS] 백준 1707 이분 그래프(c++)

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

문제 풀이를 하기 전에 이분 그래프에 대해 간략히 설명드리겠습니다. 

 

이분 그래프 (Bipartite Grpah)

• 그래프의 한 종류로, 인접한 꼭짓점을 서로 다른 색으로 칠할 때 두 가지 색으로만 칠할 수 있는 그래프
• 꼭짓점들의 집합 V와 변들의 집합 E로 이루어진 그래프 G = (V, E)가 이분 그래프라면, 꼭짓점들의 집합 V가 두 집합 A, B(두 개의 그룹)로  나눠져 E에 속한 모든 변들이 A와 B 사이에만 존재하도록 할 수 있는 것을 의미

이분 그래프 예시

V = {1, 2, 3, 4, 5, 6}

E = {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {3, 6}, {4, 5}, {5, 6}}

 

다음 그래프를 봤을 때, 모든 변(간선)이 A, B 사이에 존재하는 것을 확인할 수 있습니다. 이러한 그래프가 전형적인 이분 그래프의 예시가 되고 만약 {2, 4}라는 간선이 추가된다면, 모든 변이 A, B 사이에 존재해야 하는 조건에 위배되기 때문에 이분 그래프가 될 수 있습니다. 

 

즉, 모든 정점이 두 개의 그룹을 순환(cycle)할 수 있는 그래프여야 합니다. 순환이란 한 꼭짓점에서 시작하여 원래의 꼭짓점으로 돌아갈 수 있는 경로를 뜻합니다.

 

이제 이분 그래프에 대해 간략하게 알아봤으니, 문제 풀이 코드에 대해 설명드리겠습니다.

 

<코드>

#include <iostream>
#include <vector>
#include <cstring>

#define RED 1
#define BLUE 2
#define MAX 20001

int V, E, K;

using namespace std;

vector<int> graph[MAX];
int visited[MAX] = {0};

void input()
{
    cin >> V >> E;
}

void initializeGraph() 
{
    for (auto &v : graph) 
    {
        v.clear();
    }

    memset(visited, 0, sizeof(visited));
}

void dfs(int now)
{
    if (visited[now] == 0)
    {
        visited[now] = RED;
    }

    for (int i = 0; i < graph[now].size(); i++)
    {
        int next = graph[now][i];

        if (visited[next] == 0)
        {
            visited[now] == RED ? (visited[next] = BLUE) : (visited[next] = RED);
            dfs(next);
        }
    }
}

bool isBipartite()
{
    for (int now = 1; now <= V; now++)
    {
        for (int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i];
            if (visited[now] == visited[next])
                return false;
        }
    }
    return true;
}

void getResult()
{
    cin >> K;
    while (K--)
    {
        input();

        initializeGraph();

        for (int i = 0; i < E; i++)
        {
            int u, v;
            cin >> u >> v;
            graph[u].emplace_back(v);
            graph[v].emplace_back(u);
        }

        for (int i = 1; i <= V; i++)
        {
            if (visited[i] == 0)
            {
                dfs(i);
            }
        }

        if (isBipartite())
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
}

void optimizeInputAndOutput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
{
    optimizeInputAndOutput();
    getResult();
    return 0;
}

 

저는 DFS를 통해 해당 문제를 풀었습니다.

1. 테스트케이스 마다 벡터 및 그룹(RED, BLUE) 초기화
2. 정점 간의 간선을 양방향으로 연결
3. 1 ~ V 까지의 정점을 모두 방문해 준 다음, 첫 번째 방문한 노드를 RED(1)로 지정해 주고 RED와 연결된 정점을 BLUE(2)로 지정
4. 이분 그래프인지 판단

 

 

<참고 자료>

https://www.ksakosmos.com/post/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0-%EB%A7%9B%EB%B3%B4%EA%B8%B0-%EC%9D%B4%EB%B6%84-%EA%B7%B8%EB%9E%98%ED%94%84

그래프 이론 맛보기 – 이분 그래프