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

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

1707번: 이분 그래프

<알고리즘 분류>

   - 그래프 탐색(Graph Search)

   - DFS(Depth First Search)

   - BFS(Breadth First Search)

   - 이분 그래프 (Bipartite Graph)

 

<풀이> 

  1. 이분 그래프란?

      인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.

      주어진 그래프가 이분그래프인지 아닌지 검사하는 방법은, 

      인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있어야 한다. 

Bipartite Graph

2. 풀이 방식은 BFS와 DFS 두 가지가 있는데, 두 가지 방법 모두 풀어봐야 한다. (귀찮더라도 꼭꼭!) 

    (1) BFS는 queue 를 이용하였고, BFS과정에서 지나가는 정점들에 대해 이전 정점과 다른 색을 무작정 칠한 뒤, 

 check() 함수를 통해 이분 그래프의 조건을 만족하는 색으로 잘 칠해졌는지를 검증하였다. 

 

     (2) DFS로 풀이한 코드는 BFS 풀이과정과 달리 check() 함수를 사용하지 않았고, 

           빨간색으로 색칠한 정점을 1,  

           파란색으로 색칠한 정점을 -1로 두어

visited[next] * visited[start]

  의 결괏값에 따라 이분그래프인지 아닌지를 바로 판단(int judge 변수 이용)하였다. 

 

<추천 문제> 

이와 유사한 문제로 1260번 - DFS와 BFS가 있다. 두 문제를 꼭 풀어보길 추천한다.

 

< BFS 이용 코드>

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

#define RED 1
#define BLUE -1

vector<int> graph[20001];
int visited[20001];
int V, E;

void BFS(int start)
{
   visited[start] = RED;
   queue <int> q;
   q.push(start);
   
   while(!q.empty()){
        int now = q.front();
        q.pop();
        for (int i=0; i<graph[now].size(); i++){
            if(visited[graph[now][i]] == 0) // graph[now][i]에는 now와 연결된 i번째 노드가 있다.
                                            //방문하지 않았다면
            {
                q.push(graph[now][i]); 

                if(visited[now] == RED) visited[graph[now][i]] = BLUE;
                else if (visited[now] == BLUE) visited[graph[now][i]] = RED;
            }
        }

   }

}

bool check()
{
    for (int i = 1; i <= V; i++)
    {
        for (int j = 0; j < graph[i].size(); j++)
        {
            if (visited[i] == visited[graph[i][j]])
                // i번째 노드와 그와 연결된 다음 노드들이 색이 모두 달라야 함. 만약 하나라도 같다면 false
                return false;
        }
    }
    return true;
}

int main()
{
    int K, u, v;
    cin >> K;

    while (K--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        //빠짐없이 방문하기 위해 노드 개수만큼 BFS 돌려줘야함
        for (int i = 1; i <= V; i++)
        {
            if (visited[i] == 0)
            {
                BFS(i);
            }
        }

        //이분그래프 검사
        if (check())
            cout << "YES\n";
        else
            cout << "NO\n";

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

 

<DFS 이용 코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int K;
int V, E;
vector <int> graph[20001];
int visited[20001] = {0,}; //미방문은 0, 빨간색(초깃값)은 1, 파란색은 -1
int judge = 1;

void dfs(int start){

    for (int i=0; i<graph[start].size(); i++){
        int next = graph[start][i];
        if((visited[next] * visited[start]) > 0){ // 인접한 노드가 모두 빨간색이거나, 파란색이라면 곱은 1이 된다. 
            judge = 0; // 0은 이분그래프가 아님. 
            return ;
        }
        else if (visited[next]*visited[start] == 0){ //next 노드가 방문하지 않았다면 
                visited[next] = -visited[start]; //next 노드에는 start노드와는 다른 색을 칠해준다 .
                dfs(next);
        }
    }

}


int main(){
    cin >> K;
    while(K--){
        cin >> V >> E;

        for (int i=0; i<E; i++){
            int x, y;
            cin >> x >> y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        for (int i=1; i<=V; i++){
            if(visited[i] == 0){ // 방문하지 않았다면
                visited[i] = 1;
                dfs(i);
            }
        }

        if (judge == 0)
            cout << "NO\n";
        else
            cout << "YES\n";


        //초기화
        judge = 1;
        memset(visited, 0, sizeof(visited));
        memset(graph, 0, sizeof(graph));



    }


}