출처 : https://www.acmicpc.net/problem/1707
이분 그래프 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 14654 | 3302 | 2002 | 21.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] != -1) continue; 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 |