C++ 백준 1707 (이분 그래프)

백준 1707 (이분 그래프)
https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

---

이분 그래프(Bipartite Graph)에 대해 모른다면 구글링을 통해 알고오자!

그러나 문제에 자세한 설명이 쓰여져 있다.

 

설명

---

이분 그래프를 쉽게 설명하자면 인접한 노드끼리는 서로 다른 집합에 속해있어야 한다. 

집합에 속해있다.. 유니온 파인드?

아니다. 집합의 개수가 두개밖에 없기때문에 유니온파인드를 쓸 필요는 없다.

 

그냥 DFS나 BFS를 돌면서 인접한 노드가 이미 방문해서 어디 집합에 속했는지 정해져있는데 그 노드와 자신노드가 속한 집합이 같다면 실패를 리턴하면 된다.

 

코드를 보며 이해해보자.

 

구현

---

쉬운 이해를 위해 속한 집합을 색으로 표현했다. (노드에 색을 칠하는 느낌)

 

모든 노드가 이어져있다는 보장이 없기 때문에 모든 노드를 시작으로 해서 BFS를 구현했다. 이때 시간을 줄이기 위해 이미 방문했던 노드(색이 칠해진 노드)는 시작노드로 하지 않는다.

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


string bfs(int v, vector <vector <int>> &graph){
    int *color = new int[v+1];
    memset(color,0,(v+1)*sizeof(int));
    queue <int> q;
    for(int u=1;u<=v;u++){
        if(color[u]!=0) continue;    
        q.push(u);
        color[u] = 1;
        while(!q.empty()){
            int curr = q.front();
            for(int i=0;i<graph[curr].size();i++){
                if(color[graph[curr][i]]==0) {
                    color[graph[curr][i]] = -color[curr];
                    q.push(graph[curr][i]);
                }
                if(color[graph[curr][i]]==color[curr]) return "NO";
            }

            q.pop();
        }
    }
    free(color);
    return "YES";
}

int main(){
    int c;
    cin>>c;
    vector <string> res;
    for(int cases = 0;cases<c;cases++){
        int a,b;
        int v,e;
        cin>>v>>e;
        vector <vector <int>> graph(v+1);
        for(int i=0;i<e;i++){
            cin>>a>>b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        res.push_back(bfs(v,graph));
    }

    for(int i=0;i<res.size();i++){
        cout<<res[i]<<"\n";
    }

    return 0;
    
}

무려 골드 4티어 문제를 쉽게 해결했다.

 

또한 BFS방식이 아닌 DFS로도 충분히 구현 가능하다.