[백준][1707번][C++] 이분 그래프

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

1707번: 이분 그래프

탐색을 통해 이분 그래프인지 아닌지 판별하는 문제이다.

 

문제에서 설명하는 이분 그래프의 설명은 다음과같다.

 

"그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다."

 

쉽게 비유를 들면 사람들이 잔뜩 있는데 사람이 각각 정점이라고 하면 남자와 여자 두 성별이 있을 때(두 성별이 각각의 집합이라고 하면) 사람들이 서로 손을 잡는데 남자는 남자끼리 손을 잡지 않고 여자는 여자끼리 손을 잡지 않은 상태인 경우가 이분 그래프인 상태이다.

 

이분 그래프의 예시

 

그렇게 손을 잡는다면 대충 [남-여-남-여-남] 이렇게 번갈아 있게 되겠다.

 

(물론 문제에서는 사람이 아니기 때문에 한 정점에 여러 정점이 연결될 수 있다.)

 

DFS로 풀이했고 노드를 하나씩 탐색할 때 마다 cheak 배열에 1또는 2로 색을 칠해주면서 탐색하게 구현했다.

 

이미 색이 칠해져있는 노드인데 직전에 탐색한 노드와 색이 같다면 색이 같은 노드가 인접해 있는 것이므로 이분 그래프가 아니라고 판단하게 했다.

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#define MAX 20002
using namespace std;
int cheak[MAX]={0,}, answer=1;
int V, E;

void dfs(vector<vector<int> >& graph, int node, int color)
{
    cheak[node]=color;
    
    for(int i=0;i<graph[node].size();i++)
    {
        if(cheak[graph[node][i]]==0)
        {
            if(color==1)
                dfs(graph,graph[node][i],2);
            else
                dfs(graph,graph[node][i],1);
        }
        else if(cheak[graph[node][i]]==color)
        {
            answer=0;
            return;
        }
    }
}

int main()
{
    int a, b;
    int K;
    scanf("%d",&K);
    while(K--)
    {
        memset(cheak,0,sizeof(cheak));
        answer=1;
        scanf("%d %d",&V,&E);
        vector<vector<int>> graph(V+1);
        for(int i=0;i<E;i++)
        {
            scanf("%d %d",&a,&b);
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        
        for(int i=1;i<=V;i++)
        {
            if(cheak[i]==0 && answer==1)
                dfs(graph,i,1);
            else if(answer==0)
                break;
        }
        
        if(answer==1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    
    return 0;
}