백준 1707번 - 이분 그래프

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

이분 그래프의 정의는 문제에 제시된 내용과 같다.
사실 처음에 이 문제를 보고 이분 그래프를 잘 몰라서 위키 백과에 검색했다.
위키 백과에 나온 말을 찾아보며 처음에 이해하기 어려웠는데 쉽게 생각하면 다음과 같다.


정점이 3개가 있다고 가정하고 각각이 연결되어 있다고 생각해보자.

 

위의 그림에서 1번 정점을 시작으로 하나의 집합을 구성했다고 가정하자.

그리고 이를 파란색 집합이라고 설정한다.

 

 

 

 

 

 

 

다음으로 1번과 연결된 2번 정점은 1번과는 반대의 집합을 가져야 한다.
그리고 이를 빨간색 집합이라고 설정한다.

 

 

 

 

 

 

다음으로 2번 정점과 연결된 3번 정점은 2번과는 반대의 집합을 가져야 한다.

여기서 빨간색의 집합의 반대인 파란색 집합을 가질 때 문제가 발생한다.
바로 1번과 3번이 연결되어 있으면서도 갖은 집합을 갖게 되는 것이다.
이런 경우에 이분 그래프라고 할 수 없게 된다.

 

그리고 이런 이분 그래프의 특징을 알게 되면서 한가지 규칙을 발견할 수 있었다.
바로 사이클이 존재하면서 사이클의 개수가 홀수 개 일 때 이분 그래프가 될 수 없다는 것이다.



그렇다고 사이클이 존재한다고 무조건 이분 그래프가 아닌 것은 아니다.
사이클이 4개로 연결되어 있다면 서로 다른 집합으로 연결될 수 있기 때문이다.




처음에 사이클을 판별해서 홀수 개인지를 확인하는 방법으로 문제에 접근하려고 했다.
그러나 아직 그래프 문제에 익숙하지 않고 해결 방법이 떠오르지 않아서 

연결된 부분이 서로 다른 집합인지 검사하는 방향으로 문제에 접근했다.
(사이클의 개수에 따라서 문제를 풀 수 있을 것 같은데 그래프 문제를 좀 더 풀고 다시 도전해야겠다)



graph 변수를 vector 자료형으로 만든 다음에 문제에 제시된 정점만큼 크기를 설정했다.
그리고 visited를 통해서 집합을 1과 -1로 표현했다. 

visited를 사용한 이유는 집합을 설정할 때 한 번이라도 방문을 했는지를 나타내기 위해 표현했는데 

0이 아닐 때 1과 -1로 집합을 나누어 표현할 수 있어서 이를 사용했다. 서로 다른 색을 의미한다고 나타내기 위해 

color라는 변수를 사용해서 visited에 값을 설정할 수 있도록 했다.



dfs로 깊이 탐색을 할 때 연결되어 있다면 visited의 값에 -1을 곱해서 서로 다른 집합이 될 수 있도록 했고 

만약에 visited 값이 존재한다면 탐색하지 않도록 했다. 




모든 깊이 탐색을 마친 후에 이분 그래프의 확인 작업을 보면
각각의 정점별로 연결된 정점의 visited 값, 1과 -1로 구분한 값이 다른지를 확인한다.
만약에 값이 같다면 같은 집합을 갖기 때문에 이분 그래프가 아니라고 판단했다.

#include <iostream>
#include <vector>
using namespace std;
 
int V,E;
vector<int> graph[20001];
vector<int> visited;
 
void dfs(int node,int color){
    
    for(int i=0;i<graph[node].size();i++){
        
        //기존의 color와 다른 색으로 연결한 뒤에 깊이 탐색
        if(!visited[graph[node][i]]){
            visited[graph[node][i]]=color*-1;
            dfs(graph[node][i],color*-1);
        }
    }
}
 
bool bipartite(){
    
    for(int i=1;i<=V;i++){
        int color=visited[i];
        
        //연결된 요소와 같은 집합(color)을 갖는지 확인
        for(int j=0;j<graph[i].size();j++){
            if(color==visited[graph[i][j]])
                return false;
        }
    }
    return true;
}
int main(){
    
    int K;
    cin>>K;
    
    while(K--){
        cin>>V>>E;
        
        int src,dest;
        for(int i=0;i<E;i++){
            scanf("%d %d",&src,&dest);
            graph[src].push_back(dest);
            graph[dest].push_back(src);
        }
        
        visited=vector<int> (V+1,0);
        
        for(int i=1;i<=V;i++){
            
            if(graph[i].size()==0)
                continue;
            
            //한번도 방문한 적 없을 때 값을 1로 설정한 다음에 dfs로 연결된 요소 확인
            if(!visited[i]){
                visited[i]=1;
                dfs(i,1);
            }
        }
        
        if(bipartite()) printf("YES\n");
        else    printf("NO\n");
        
        for(int i=1;i<=V;i++)
            graph[i].clear();
        
    }
    
    
    return 0;
}