Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
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
Archives
Today
Total
관리 메뉴

차근차근

[백준 1707] 이분 그래프 본문

대학교/Algorithm

[백준 1707] 이분 그래프

SWKo 2020. 2. 1. 17:10

0. 제목

  • 백준 1707 이분 그래프
  • BOJ 1707 이분 그래프
  • C++ 1707 이분 그래프

1. 문제

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


2. 풀이

  • DFS, BFS 두가지 방법으로 풀 수 있다.
  • 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다고 문제에 정의되어 있다.
  • 각 단계마다 색을 칠하는데 color 가 0이면 아직 방문하지 않은 것이고 1과 2로 색을 표현하였다.
  • 이분 그래프 여부를 판단하는 함수에서는 다음 단계로 갈때 같은 색깔을 가지고 있으면 false를 반환하고 그것이 아니면 true를 반환하도록 하였다.

 


3. 코드

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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
vector<int> connect[20001];
int nodeColor[20001];
int K, V, E;
 
void dfs(int nodeNum, int color);
bool isBipartite(void);
 
int main(int argc, const char * argv[]) {
    int a, b;
    
    cin >> K;
    
    for(int i = 0; i < K; i++){
        for (int j = 1; j < 20001; j++)
            connect[j].clear(); // 케이스마다 초기화시켜줘야 함
        memset(nodeColor, 0sizeof(nodeColor)); //케이스마다 초기화시켜줘야 함
        
        cin >> V >> E;
        for(int j = 0; j < E; j++){
            cin >> a >> b;
            connect[a].push_back(b);
            connect[b].push_back(a);
        }
        
        for(int j = 1; j <= V; j++){
            if(nodeColor[j] == 0)
                dfs(j, 1); // 1번 색깔부터 시작
        }
        
        if(isBipartite())
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    
    return 0;
}
 
//color 가 0 이면 아직 방문하지 않은 것이고 1, 2 를 각 색깔로 둔다.
void dfs(int nodeNum, int color){
    nodeColor[nodeNum] = color;
    unsigned long int size = connect[nodeNum].size();
    for(unsigned long int i = 0; i < size; i++){
        int next = connect[nodeNum][i];
        if(!nodeColor[next])
            dfs(next, 3 - color);
    }
}
 
bool isBipartite(void){
    for(int i = 1; i <= V; i++){
        unsigned long int size = connect[i].size();
        for(unsigned long int j = 0; j < size; j++){
            int next = connect[i][j];
            if(nodeColor[i] == nodeColor[next])
                return false;
        }
    }
    return true;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 10451] 순열 사이클  (0) 2020.02.02
[백준 1912] 연속합  (0) 2020.02.01
[백준 11724] 연결 요소의 개수  (0) 2020.01.29
[백준 2750] 수 정렬하기  (0) 2020.01.28
[정렬] 버블 정렬  (0) 2020.01.28
Comments