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

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

1707번: 이분 그래프

 

문제

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

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

 

 

접근방식 및 고려사항

- BFS 로 해결가능하다.

- 이분 그래프의 특성상 BFS를 진행하면서 0과 1을 번갈아 가면서 체크해준다.

- 체크하는 과정에서 만약 인접한 노드가 현재노드의 체크값과 같으면 이분그래프가 아닌것이다.

- 주어진 인풋이 완전한 하나의 그래프가 아닐수도 있으므로 모든 정점에 대해 탐색하면서 방문하지 않은 노드들에 대해서 모두 bfs를 시행해야 한다.

- 한번 이분그래프가 아니라는 결과가 도출되었으면 다음탐색하는 그래프가 이분그래프인지 여부와 상관없이 NO를 출력해야 한다. 이부분을 처음에 고려하지 못했다.

 

#include <iostream>
#include <queue>
#include <vector>
#define vMAX 20005 // 범위설정 잘못함 20000 -> 20001
using namespace std;

int check[vMAX];

bool bfs(int start, vector<int> a[]){
    queue<pair<int, int>> q;
    bool result = true;
    q.push({start, 1});
    check[start]=1;
    while(!q.empty()){
        int x = q.front().first;
        int cnt = q.front().second;
        int ch = check[x];
        q.pop();
        for(int i=0; i<a[x].size(); i++){
            int c = a[x][i];
            if(check[c]==ch) result = false;
            if(check[c]==-1){
                check[c] = (cnt+1)%2;
                q.push({c,cnt+1});
            }
            //printf("x:%d, ch:%d, check[%d]:%d\n", x,ch,c,check[c]);
        }
    }
    
    return result;
}

int main()
{
    int t; cin >> t;
    for(int k=0; k<t; k++){
        int v,e; cin >> v >> e;
        vector<int> a[vMAX];
        bool result=true;
        for(int x,y,i=0; i<e; i++){
            cin >> x >> y;
            a[x].push_back(y);
            a[y].push_back(x);
        }
        
        for(int i=1; i<=vMAX; i++)
            check[i]=-1;
        
        for(int i=1; i<=v; i++){ // 1부터 시작해서 v와 같을때 까지 해야하는데 범위 설정을 잘못해서 오답이 나왔음.
        // + 이미 한번 false인 상황이면 이를 고정시켜야 하는데 result = bfs()로 해서 마지막 bfs가 답으로 출력되는 상황이 되었었음. 
            //printf("%d\n",i);
            if(check[i]==-1){
                if(bfs(i, a)==false)
                    result = false;
                //printf("%d번째 - in : %d\n",k+1,i);
            }
        }
        if(result==false){
            printf("NO\n");
        }else{
            printf("YES\n");
        }
    }
    
    return 0;
}

느낀점

배열 인덱스 설정하는 부분과 한번 이분그래프 판정이 났으면 답을 유지해야 하는 부분 등 세밀한 것들을 자꾸 놓치게 된다. 문제조건과 생각을 더 꼼꼼하게 체크할 필요가 있다고 느꼈다.