[백준/Baekjoon] 1707 이분 그래프 C++ :: Bipartite Graph & BFS & DFS

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

1707번: 이분 그래프

---

1. Logic

나를 이분그래프에 처음 입문시켜준 문제이다.

이분그래프란 서로 인접한 노드를 다른 그룹으로 묶을 때 서로 겹치지 않고 두개의 그룹으로 정확히 나눠지는 그래프의 형태를 말한다.

아래의 두번째 그림을 보면 좌측 노드 3개를 l1, l2, l3 / 우측 노드 3개를 r1, r2, r3라고 했을 때 우측에서 처음 시작하면 l1이 1번 그룹 서로 인접한 r1, r2, r3는 -1번 그룹 다시 r1, r2, r3와 각각 인접한 l1, l2, l3는 1번 그룹에 모이게 된다. 즉 어떻게 해도 인접한 노드끼리 1번 그룹과 -1번 그룹에 동시에 들어가는 일이 생기지 않는다.

1번 그룹, -1번 그룹으로 위에서 설명한 이유는 코딩을 짤 때 코드쓰기 편해서이다. 서로의 그룹을 둘로만 나누면 되기 떄문에 true/false와 같이 나눠도 되고 1/2(next%2+1)로 나누는 사람도 있었다. 이건 각자 정하기 나름인 듯 하다.

728x90

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<int> graph[20001];
int vis[20001];

int v, e;
bool isBipartite;

void bfs(int node) {
    queue<int> q;
    
    q.push(node);
    vis[node] = 1;
    
    while(!q.empty()) {
        int cur = q.front();
        int nColor = vis[cur];
        q.pop();
        
        for(int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i];
            if(vis[next] == nColor) {
                isBipartite = true;
                return;
            }
            else if (!vis[next]){
                vis[next] = -nColor;
                q.push(next);
            }
        }
    }
}

void dfs(int cur, int choice) {
    vis[cur] = choice;
    
    for(int next : graph[cur]) {
        if(vis[next] == vis[cur]) {
            isBipartite = true;
            return;
        }
        
        if(!vis[next]) {
            vis[next] = -choice;
            dfs(next, -choice);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    
    while(t--) {
        cin >> v >> e;
        isBipartite = false;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i <= v; i++) {
            graph[i].clear();
        }
        
        int s1, s2;
        for(int i = 0; i < e; i++) {
            cin >> s1 >> s2;
            
            graph[s1].push_back(s2);
            graph[s2].push_back(s1);
        }
        
        for(int i = 1; i <= v; i++) {
            if(vis[i]) continue;
            //bfs(i);
            dfs(i, 1);
        }
        
        if(!isBipartite) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐