[백준 1707] 알고리즘 89일차 : 이분 그래프

www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

C++ BFS

그래프 문제

 

접근방법

일단 정점을 담는 두 집합이 있다고 가정하고, 처음엔 그래프를 탐색하면서 인접한 노드는 다른 집합에 넣고

마지막에 두 집합의 교집합이 공집합이 아닌지 확인해서 결과를 출력했다.

근데 이렇게 하면 우선 이 문제에서 그래프는 모든 경우 연결그래프라고 가정하고 있지 않고, 무엇보다 시간초과가 났다.

그래서 갈아엎었다 ^_^

방문여부를 저장하는 배열에 0,-1,1을 저장했다.

방문하지 않은 경우 : 0 / 방문했고 A집합에 속하는 경우 : 1 / 방문했고 B집합에 속하는 경우 : -1

bfs함수에서 인접한 노드를 큐에 푸시하면서 해당 노드가 속한 집합을 표시하는데 이때 이미 방문되어서 인접노드끼리 같은 집합에 속하는 경우 false를 리턴한다. -> 이분 그래프가 아니라는 것

그리고 연결 그래프가 아니라 하나의 그래프가 끝나도 정점 중에 아직 방문 되지 않은 정점에 대해서도 bfs를 돌게했다.

 

오답노트

일단 코드를 크게 갈아엎은 이유는 위에 썼고

바꾼 로직으로 돌려도 시간초과나길래 정말 의아해했지만 다른분 코드 둘러보다가

bfs함수가 받는 매개변수 중에 벡터가 있는데 그걸 주소값으로 안받았다고 시간초과가 났다.

벡터는 call by reference로 받지 않으면 call by value로 전달되고 &를 붙여주면 call by reference로 전달된다.

 

값이 제대로 나온 이유는 (에러나지 않은 이유) 그냥 안해도 될 계산을 더 할 뿐이지 결과에는 지장이 없기 때문..

시간초과 난 이유는 복사하는데 오버헤드가 들어간 것도 영향이 있겠지만,

이렇게 되면 방문한 노드도 방문하지 않은 노드가 되고 그럼 모든 노드에 대해서 bfs를 모두 돌게 된다..

시간초과 날만하네요.

 

소스코드

 

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

bool bfs(int firstNode, vector<int>& visit, vector<vector<int>>& adj){
    queue<int> q;
    q.push(firstNode);
    visit[firstNode] = 1;
    while(!q.empty()){
        int here = q.front();
        int sign = -1 * visit[here]; //반대
        q.pop();
        int there;
        for(long p = 0 ; p < adj[here].size() ; p++){
            there = adj[here][p];
            if(visit[there] == 0){
                q.push(there);
                visit[there] = sign;
            }else if(visit[there] == visit[here]){
                return false;
            }
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    int v,e;
    for(int i = 0 ; i < t ; i++){
        cin >> v >> e;
        vector<vector<int>> adj(v,vector<int>());
        vector<int> visit(v,0);
        int a,u;
        for(int j = 0 ; j < e ; j++){
            cin >> a >> u;
            adj[--a].push_back(--u);
            adj[u].push_back(a);
        }
        bool isBipatite = true;
        for(int vv = 0 ; vv < v ; vv++){
            if(visit[vv] == 0){
                if(!bfs(vv, visit, adj)){
                    isBipatite = false;
                    break;
                }
            }
        }
        cout << (isBipatite ? "YES\n" : "NO\n");
    }
    return 0;
}