[백준] 1707번 C/C++ 풀이 _ 이분 그래프

 


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

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB146543302200221.804%

문제

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

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

입력

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

출력

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

예제 입력 1 

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2

예제 출력 1 

YES
NO

출처

알고리즘 분류

풀이

저는 이 문제를 BFS 를 이용하여 해결했습니다.
이분 그래프의 특징은 같은 그룹에 속한 요소들 끼리는 연결하지 않는다는 것입니다. 


위와 같은 구성으로 시작점을 기준으로 BFS 를 진행하면서, 자식 노드들을 살펴봅니다.
자식 노드들의 상태에 따라서 노드에 번호를 번갈아 가면서 매겨줍니다. 
BFS의 각 라운드가 진행 될 때마다, 위의 노드에서 같은 색으로 표시한 노드들을 같은 번호로 기록합니다.

- 노드의 자식이 아무 그룹도 없는 경우 : 다음 그룹의 번호를 매긴다.
- 노드의 자식이 그룹이 있는 경우
  >> 그룹이 부모의 그룹 번호와 다르다 -> 올바른 상태이기 때문에 넘어간다. 
  >> 그룹이 부모의 그룹 번호와 같다    -> 이분 그래프를 만족하지 못하기 때문에, 종료한다. 

위의 문제에서 하나의 주의 사항이 있습니다.
1번 노드에서 시작한다고 해서 반드시 바로 정답이 나오는 것이 아닙니다.
아래의 예시를 보면 1~3 이 연결되어 있고, 4~6이 연결되어 있기 때문에 4에서도 이분 탐색인지 확인하는 과정이 필요합니다. 

그래서 각 노드별로 이분 탐색인지 확인하는 과정이 필요합니다.

자세한 구현은 소스코드를 참조해주세요.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
 
enum NodeGroup{
    G_A, G_B
};
 
int is_bipartite(vector<vector<int>> &_edge_vec, int _V) {
    vector<int> node_group(_V + 1-1);
    for (int start_node = 1; start_node <= _V; start_node++) {
        queue<int> bfs_queue;
        bfs_queue.push(start_node);
        if (node_group[start_node] != -1continue;
 
        int now_group = G_A, next_group = G_B;
        node_group[start_node] = G_A;
 
        int bfs_size = bfs_queue.size();
        while (bfs_size--) {
            int now_node = bfs_queue.front(); bfs_queue.pop();
 
            for (auto next_node : _edge_vec[now_node]) {
                // 방문한 노드면 색깔 확인
                if (node_group[next_node] != -1)
                    if (node_group[next_node] == now_group) return 0;
                    else continue;
 
                    // 방문하지 않은 노드면, 색깔을 넣고 큐로 넣는다.
                    node_group[next_node] = next_group;
                    bfs_queue.push(next_node);
            }
 
            if (bfs_size == 0) {
                bfs_size = bfs_queue.size();
                now_group = next_group;
                next_group = (now_group == G_A ? G_B : G_A);
            }
        }
    }
    return 1;
}
 
int main() {
    int T; scanf("%d"&T);
    while (T--) {
        int V, E; scanf("%d %d"&V, &E);
        vector<vector<int>> edge_vec(V+1);
        for (int e_idx = 0; e_idx < E; e_idx++) {
            int node_1, node_2; scanf("%d %d"&node_1, &node_2); 
            edge_vec[node_1].push_back(node_2);
            edge_vec[node_2].push_back(node_1);
        }
        if (is_bipartite(edge_vec, V)) printf("YES\n");
        else  printf("NO\n");
    }
    return 0;
}
cs