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

백준 1707 : 이분 그래프
난이도 : 골드 4

시간 : 1시간 소요

 

 

 

문제

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

1707번: 이분 그래프

 

풀이 과정

 

bfs를 사용해서 풀 수 있는 문제이다. 

초기에는 2차원 배열로 풀어볼까 생각했지만 입력값의 크기가 2만이라 2차원 배열을 만들면 제한 용량을 넘긴다.

그래서 vector<int> board[MAX] 로 1차원 배열로 벡터를 만들어서 구현했다.

 

먼저 입력 t1,t2를 받으면 t1,t2 배열에 각각 저장한다.

그 후 1번 정점부터 방문 하지 않았으면 방문처리를 해주고, 해당 정점을 기준으로 bfs를 시켜준다.

group[MAX] 배열을 선언하여 1번 정점은 1를 저장하고, 1번 정점과 인접해 있는 정점은 -1를 저장시킨다.

 

만약 특정 정점(A)과 이웃한 정점(B)이 이미 방문한 정점(visited[B] == 1)인데 group[MAX] 의 값이 1 이나 -1로 동일하다면,

이는 두 그룹으로 나눌 수 없을 의미하기 때문에 false를 반환하고, NO를 출력한다.

 

이 조건에 걸리지 않는다면, 두 그룹으로 나눌 수 있다는 의미이기 때문에 YES를 출력한다.

 

 

최종 코드

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

#define MAX 20001

using namespace::std;

int K, V, E;
vector<int> board[MAX];
int visited[MAX];
int group[MAX];

queue<int> q;

bool bfs(){
    
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        
        for(auto i : board[t]){
            if(visited[i] == 0){
                q.push(i);
                visited[i] = 1;
                group[i] = group[t] * -1;
            }else if(group[t] == group[i]){
                return false;
            }
        }
        
    }
    return true;
}

int main(){
    scanf("%d", &K);
    
    for(int i=0; i<K; i++){
        scanf("%d %d", &V, &E);
        for(int j=0; j<E; j++){
            int t1,t2;
            scanf("%d %d", &t1, &t2);
            board[t1].push_back(t2);
            board[t2].push_back(t1);
        }
        
        bool check = true;
        for(int j=1; j<=V; j++){
            if(visited[j] == 0){
                q.push(j);
                visited[j] = 1;
                group[j] = 1;
            }
            if(!bfs()){
                check = false;
                break;
            }
        }
            
        if(check){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
        
        
        memset(board, 0, sizeof(board));
        memset(visited, 0, sizeof(visited));
        memset(group, 0, sizeof(group));
        while(!q.empty()){
            q.pop();
        }
        
    }
}