문제 링크입니다 https://www.acmicpc.net/problem/1707
1707번: 이분 그래프
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어
www.acmicpc.net
11724번 '연결 요소의 개수' 문제와 동일하게 BFS, DFS 중 어느 것이든 상관없는 문제였습니다. DFS를 사용하여 문제를 해결하였고, color 배열을 만들어 1과 2로 나누어 각 정점에 부여하면서 나와 인접한 노드가 같은 color를 가지고 있으면 틀린 경우로 인식하도록 구현했습니다. 자세한 설명은 주석 참고해주세요!
* DFS를 통한 그래프 순회를 한 번만 하지 않고 color가 0인 정점에 대해 하는 이유는 하나의 테스트 케이스 안에서 나누어진 그래프 2개 이상이 입력으로 주어질수도 있기 때문입니다.
[소스코드]
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int MAX = 20000 + 10;
// 이분 그래프인지 아닌지 판별해주는 flag
bool flag;
// 방문 처리와 동시에 해당 정점에
// 색깔을 1 또는 2로 부여하기 위한 color배열
int v, e, color[MAX];
vector <int> graph[MAX];
// 정점 node부터 시작하여 dfs를 통해 그래프 순회를 하고,
// 각 정점에 해당하는 색깔 c를 color배열에 넣고,
// 나와 인접한 노드가 나랑 색깔이 같으면
// flag를 false로 만드는 함수
void dfs(int node, int c) {
color[node] = c;
// 나와 인접한 모든 노드에 대해
for (int i = 0; i < graph[node].size(); i++) {
int next = graph[node][i];
// 나와 인접한 노드와 내가 색깔이 같다면
if (color[next] == color[node]) {
flag = false; // 이분 그래프가 될 수 없습니다
return;
}
// c에 초기값이 1이고 3-c를 하면 2가 되고,
// c가 2이면 3-c가 다시 1이 됩니다
// 그래서 방문하게 되는 노드들은
// 1 또는 2의 color를 부여받습니다
if (!color[next]) dfs(next, 3 - c);
}
}
int main(void) {
int tc;
scanf("%d", &tc);
for (int t = 0; t < tc; t++) {
scanf("%d%d", &v, &e);
// 각 테스트 케이스마다 color 배열과 graph를 초기화합니다
memset(color, 0, sizeof(color));
for (int i = 1; i <= v; i++)
graph[i].clear();
// 그래프를 만듭니다
for (int i = 0; i < e; i++) {
int a, b;
scanf("%d%d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
}
// flag가 dfs 함수 안에서 false가 되면 이분 그래프가 아닙니다
flag = true;
// 1번 정점부터 v번 정점까지
for (int i = 1; i <= v; i++) {
// color를 부여받지 못한(아직 방문처리가 안된) 노드에 대해
// dfs를 수행하고 flag를 확인합니다
if (!color[i]) {
dfs(i, 1);
if (!flag) break;
}
}
if (flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}
|
cs |

'알고리즘 > BaekJoon' 카테고리의 다른 글
백준 4963 : 섬의 개수 (0) | 2020.02.26 |
---|---|
백준 2667 : 단지 번호 붙이기 (0) | 2020.02.25 |
백준 11724 : 연결 요소의 개수 (0) | 2020.02.25 |
백준 15658 : 연산자 끼워넣기 (2) (0) | 2020.02.25 |
백준 1182 : 부분수열의 합 (0) | 2020.02.25 |