[풀이]
백준 사이트의 정답률은 작성 당시 22퍼센트 밖에 안되서 지레 겁먹을수 있으나!
이분 그래프의 개념만 알면 bfs 혹은 dfs로 쉽게 풀수 있는 문제 입니다!!
문제의 설명만 보면 뭐가 이분그래프인지 잘 모르겠는데요, 그림을 보면 바로 알 수 있습니다!
위 그림 처럼 색이 서로 다르게 칠해질 수 있어야 이분 그래프 입니다.
쉽게 말해 니편 내편 가를 수 있어야 한다는 것입니다 ㅎㅎ
저는 bfs로 풀이 했는데요, 현재 노드가 1번 팀이라면 다음 노드는 2번 팀 이런식으로 팀을 구분 했고,
만약 팀이 겹치게 된다면 바로 false를 리턴했습니다.
아래는 풀이한 코드입니다 :)
|
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
|
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> visited(20001, 0);
bool bfs(vector<vector<int>> g, int v) {
queue<int> q;
visited[v] = 1;
q.push(v);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto x : g[cur]) {
if (!visited[x]) {
// 편가르기!!
visited[x] = (visited[cur] == 1 ? 2 : 1);
q.push(x);
}
else if (visited[x] == visited[cur])
return false;
}
}
return true;
}
int main(void) {
int k;
cin >> k;
while (k-- > 0) {
int v, e;
cin >> v >> e;
vector<vector<int>> g(v + 1);
for (int i = 1; i <= v; i++) visited[i] = 0;
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
bool flag = true;
for (int i = 1; i <= v; i++) {
if (visited[i] == 0) {
if (!bfs(g, i)) {
flag = false;
break;
}
}
}
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}
|
cs |
|
|
|
질문이나 지적사항은 댓글 부탁드립니다 :)
'알고리즘 > BOJ' 카테고리의 다른 글
| [백준] 9251번 LCS (0) | 2020.05.06 |
|---|---|
| [백준] 2206번 벽 부수고 이동하기 (2) | 2020.04.25 |
| [백준] 13460번 구슬 탈출 2 (0) | 2019.09.15 |
| [백준] 2583번 영역 구하기 (0) | 2019.09.11 |
| [백준] 14502번 연구소 (0) | 2019.09.11 |
