Beakjoon 1707 이분 그래프

22 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1707

나의 풀이

이분 그래프는 같은 집합에 속한 정접끼리는 서로 인접하지 않는다. 즉 인접한 정점은 항상 다른 집합에 속하게 된다는 것을 의미한다.
이를 이용하면 dfs로 그래프 탐색을 할 때 각 정점의 group을 결정하게 된다.
여기서 group은 이분 그래프에서의 2개의 집합을 의미하며 -1 또는 1의 값을 갖도록 하였다.
앞서 말했듯 인접한 정점은 항상 다른 집합에 속하기 때문에 초기 group 값이 정해진다면 그래프를 탐색하며 모든 정점의 group 값을 구할 수 있고 이 과정에서 group 값이 충돌하여 -1과 1 동시에 만족해야 하는 경우 이분 그래프가 불가능하다고 판단한다.

예를 들어 위와 같은 그래프 구조가 있을 때 정점 1의 초기 group 값을 1로 생각하면 정점 3과 4의 group 값은 -1이고, 정점 4에 의해 정점 2의 group 값은 1이 된다. 이 과정에서 group 값의 충돌이 없기 때문에 이 그래프를 이분 그래프라고 할 수 있다.

이 그래프도 마찬가지로 정점 1의 초기 group 값을 1로 생각하면 정점 2의 group 값은 -1이 되고, 정점 2에 의해 정점 3과 정점 4의 group 값이 1이 된다. 이 과정에서 정점 3과 정점 4 사이의 group 값 충돌이 생기기 때문에 이 그래프는 이분 그래프라고 할 수 없다. 위 그래프와 같이 단절된 그래프가 생길 수 있기 때문에 모든 정점에 대해 그래프 탐색을 해야한다. 만약 정점이 하나만 존재한다면 2개의 집합을 만들 수 없기 때문에 항상 이분 그래프가 아니다.

풀이 코드 : 1707 이분 그래프

#include <stdio.h>
#include <vector>

using namespace std;

vector<vector<int>> edge;
vector<int> visit;
vector<int> group;

bool dfs(int start){
    vector<int> stack;
    stack.push_back(start);
    group[start] = 1;
    while(!stack.empty()){
        int curr = stack.back();
        stack.pop_back();

        if(visit[curr] == 0){
            visit[curr] = 1;
            for(int i=0;i<edge[curr].size();i++){
                int next = edge[curr][i];
                if(group[next] == 0){
                    group[next] = -group[curr];
                }
                else if(group[next] == group[curr]){
                    return false;
                }
                if(visit[next] == 0){
                    stack.push_back(next);
                }
            }
        }
    }
    return true;

}


int main(){
    int K, V, E;
    int first, second;
    scanf("%d", &K);
    for(int t=0;t<K;t++){
        scanf("%d %d", &V, &E);
        
        edge.resize(V+1);
        visit.resize(V+1);
        group.resize(V+1);
        
        for(int i=0;i<E;i++){
            scanf("%d %d", &first, &second);
            edge[first].push_back(second);
            edge[second].push_back(first);
        }

        bool answer = true;
        for(int i=0;i<V;i++){
            if(visit[i] == 0) {
                answer = dfs(i);
                if(!answer) break;
            } 
        }

        if(!answer || V == 1){
            printf("NO\n");
        }else{
            printf("YES\n");
        }


        group.clear();
        edge.clear();
        visit.clear();
    }
}

채점결과