JArchive 프로그래밍 일기

문제

이분 그래프 백준 1707번

리뷰

이분 그래프는 정점이 전부 RED, BLUE 2가지 색상으로만 구성됬다고 했을 때, 인접 정점 끼리는 다른 색깔을 가지는 그래프다.

이분 그래프가 뭔지 헷갈려서 여러 포스팅을 찾아봤다.

참고. DFS로 이분그래프를 구현한 코드

코드는 BFS로 짰고, 시작정점 색을 RED로 시작했다.

시작정점의 인접한 정점들은 전부 BLUE로 칠한다. (시작정점이 BLUE라면, 인접한 것들은 RED로.)

BFS 탐색으로 모든 정점색을 정해주고나면, is_bipartite 함수로 이분 그래프인지 판단한다.

기준은 특정 정점을 기준으로 인접한 정점들이 전부 다른 색을 갖는지 확인한다.

즉, i 를 정점이 RED라면, i의 인접 정점들은 전부 BLUE 여야만 한다.

그게 아니라면, 이분그래프의 조건을 만족하지 않는다.

연결 그래프가 아닐 수 있으므로 BFS탐색은 모든 정점을 시작점으로 해서 확인해야 한다.

코드

#include <iostream> 
#include <vector>
#include <queue>
#include <cstring> // memset()
#include <algorithm>
#define MAX_SIZE 20000+1
#define RED 1
#define BLUE 2
using namespace std;


int K, V, E;
vector<int> M[MAX_SIZE];
int check[MAX_SIZE]; // 미방문 0 , RED 1 , BLUE 2  

void BFS(int v){ // 시작노드와 인접한 노드들은 시작노드와 반대되는 색으로 칠한다.  

    queue<int> q;

    int color = RED; // 시작 노드 RED
    bool is_bipartite = true;

    check[v] = color;
    q.push(v);

    while(!q.empty()){

        int now = q.front();
        q.pop();

        if(check[now] == RED){  // 현재노드와 다른 색깔로 정한다
            color = BLUE;  
        }else{
            color = RED;
        }

        int adj_size = M[now].size();

        for(int i = 0; i < adj_size; i++){

            int next = M[now][i];

            if(!check[next]){ 
                check[next] = color;
                q.push(next);
            }
        }
    }

}

bool is_bipartite(){ // 이분 그래프인지 확인 

    for(int i = 1; i <= V; i++ ){ // 모든 정점 확인 

        int adj_size = M[i].size();
        for(int j = 0; j < adj_size; j++ ){
            int next = M[i][j];
            if(check[i] == check[next]){
                return 0;  // 인접 정점끼리 같은 색깔이면 이분 그래프가 아니다. 
            }
        }
    }

    return 1;
}

int main(void){

    int st, end = 0;

    cin >> K;

    while(K--){

        cin >> V >> E;

        while(E--){ // 간선         
            cin >> st >> end;
            M[st].push_back(end);
            M[end].push_back(st);
        } // 입력받기 끝  

        for(int i = 1; i <= V; i++){ // 모든 정점에서 시작해본다. 연결 그래프가 아닐수 있기 때문이다.
            if(!check[i]){ // 미방문이라면, 탐색시작 
                BFS(i);
            }
        }

        string answer = (is_bipartite()) ? "YES" : "NO";
        cout << answer << '\n';

        memset(check, 0, sizeof(check)); // 초기화  
        for(int i = 0; i <= V; i++){ // 초기화  
            M[i].clear();
        }
    }

    return 0;    
}