[백준(BOJ)] 1707번: 이분 그래프 (DFS/BFS, C++)

📝 문제풀이 과정

---

BOJ:11724(연결 요소의 개수) 문제와 유사하다.

이 문제에서는 아래와 같은 조건을 확인하는 과정이 추가된다.

 

이분 그래프 확인 방법

1. 서로 인접한 정점은 서로 다른 색이다.
   • 현재 탐색을 시작한 정점과 인접한 정점은 +, -로 다른 부호를 준다.
   • 현재 탐색한 정점의 값이 current이면, 해당 정점에는 current 값을 주고, 해당 정점과 인접한 정점은 -current를 줘서 서로 다른 그룹에 속하도록 한다.
2. 정점과 인접한 정점을 방문할 때 만약 같은 색이라면 이분 그래프가 아니다.
   • 현재 탐색 정점과 인접한 정점 중에서 이미 방문을 했고(color[num] != 0), color[num] + color[current] != 0이 아니라면 같은 그룹에 속하는 것으로 이분 그래프가 아니다. 따라서 CheckBipartite = false로 주고 리턴한다.

 

모든 정점이 서로 연결되어 있지 않고, 아예 연결 그래프가 아닐 수도 있기 때문에, 초기 하나만 값을 줘서 탐색을 하지 않고 방문하지 않은 모든 정점에 대해 BFS 탐색을 했다.

 

 

💻 C++ 제출코드

---

#include <bits/stdc++.h> //<stdio.h><stack><queue><deque>
using namespace std;

void DFS(int start, deque<int> *graph, int *color, bool *CheckBipartite){
    stack<int> s;
    color[start] = start;
    s.push(start);

    while(!s.empty()){
        int current = s.top();
        s.pop();
        for(int next: graph[current]){
            if(color[next] == 0){
                s.push(current);
                s.push(next);
                color[next] = color[current]*-1;
            }
            else if(color[next] + color[current] != 0){
                *CheckBipartite = false;
                return;
            }
        }
    }
}

void BFS(int start, deque<int> *graph, int *color, bool *CheckBipartite){
    queue<int> q;
    color[start] = start; // +start
    q.push(start);
    //printf("[+] %d visited. color[%d] = %d\n", start, start, color[start]);

    while(!q.empty()){
        int current = q.front();
        q.pop();
        for(int num: graph[current]){
            if(color[num] == 0){ // if not visited
                q.push(num);
                color[num] = color[current]*-1; // -start 
                //printf("[+] %d visited. color[%d] = %d\n", num, num, color[num]);
            }
            else if(color[num] + color[current] != 0) {
                *CheckBipartite = false;
                return; 
            }
        }
    }
}

int main(){
    int K; // K: 테스트 케이스의 개수
    scanf("%d", &K);

    for(int i=0; i<K; i++){
        int V, E; // V: 정점의 개수, E: 간선의 개수
        scanf("%d %d", &V, &E);
        
        deque<int> graph[V+1];
        int color[V+1]; // check not visitied by 0
        bool CheckBipartite = true;
        fill(color, color+V+1, 0); // initialize

        for(int j=0; j<E; j++){
            int u, v;
            scanf("%d %d", &u, &v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        for(int j=1; j<=V; j++){
            if(CheckBipartite == false) break;
            if(color[j] == 0) BFS(j, graph, color, &CheckBipartite);
            //if(color[j] == 0) DFS(j, graph, color, &CheckBipartite);
        }
        printf("%s\n", CheckBipartite == true ? "YES" : "NO");
    }
}

DFS의 경우, stack으로 구현해서 인접한 노드 push 전 current도 넣어서 current의 자식노드까지 먼저 탐색 후 인접노드를 탐색하도록 했다.

 

 

👏 결과

---