[c++] 백준 1707 이분 그래프

여전히 맥락없는 지피티....

 

❔ 문제

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

 

🔍 문제 요약

• 목표: 그래프의 정점 집합을 두 개로 나누었을 때,같은 집합에 속한 정점끼리는 인접하지 않도록 분할이 가능하면 이분 그래프라고 한다. 입력으로 주어진 그래프들이 이분 그래프인지 아닌지 판별하라.
  

• 입력
  • 테스트 케이스 개수 K. 각 테스트 케이스마다
  • 정점의 개수 V (1 ≤ V ≤ 20,000)
  • 간선의 개수 E (1 ≤ E ≤ 200,000)
  • E개의 간선 정보: u v (1 ≤ u, v ≤ V)
• 출력 : 각 그래프가 이분 그래프인지 여부를 YES 또는 NO로 출력
  

 

---

⛔️ 초기시도 (맞긴 함)

#include<iostream>
#include<vector>
#include<queue>
# define MAX 20'001
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int t; cin>>t;
    while(t--){
        int v,e,isAble=1; cin>>v>>e; //그래프의 정점의 개수 V, 간선의 개수 E
        vector<vector<int>> graph(v+1);

        // 간선 입력 받기 
        for(int i=0,a,b;i<e;i++){
            cin>>a>>b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        //BFS
        queue<pair<int,int>> q; // 노드, 추가하려 시도할 그룹
        int visit[MAX]={0,};
        int V1[MAX]={0,}; // 그룹 1
        int V2[MAX]={0,}; // 그룹 2

        for(int i=1;i<=v;i++){
            if(visit[i]) continue;

            q.push({i,1}); visit[i]=1;
            while(q.size()){
                int node = q.front().first;
                int group = q.front().second;
                q.pop();

                // 1번 그룹에 넣기 시도 
                if(group ==1){
                    for(auto adj : graph[node]){
                        // 해당 그룹에 adj가 이미 들어가 있으면 이분 그래프가 될 수 없음 
                        if(V1[adj]){ isAble=0; break; }

                        // 아직 방문 안했으면 큐에 추가 
                        if(!visit[adj]){ q.push({adj,2}); visit[adj]=1; } 
                    }
                    V1[node]=1; // 1번 그룹에 node 추가 
                }
                // 2번 그룹에 넣기 시도 
                else{
                    for(auto adj : graph[node]){
                        if(V2[adj]){ isAble=0; break; }
                        if(!visit[adj]){ q.push({adj,1}); visit[adj]=1; } 
                    }
                    V2[node]=1; // 2번 그룹에 node 추가 
                }
                if(!isAble) break;
            }
        }
        
        //이분 그래프이면 YES, 아니면 NO
        if(isAble) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
}

• 각 그룹을 따로 관리하느라 불필요한 메모리 사용
• 총 정점 수가 최대 2만인데, 그룹 배열이 2개라 메모리 이중 낭비

 

 

---

🔑 해결 전략 : BFS

 

💙 Step 1: 그룹을 depth 값으로 처리

int v[MAX] = {0};  // depth 기록, 짝수/홀수로 그룹 구분

• depth % 2를 이용해 현재 정점의 그룹을 자동으로 판단
• 1, 2, 3… 으로 레벨을 부여하면
  • 짝수 → 그룹 0
  • 홀수 → 그룹 1

 

💙 Step 2 : 같은 그룹인지 확인

if (v[adj] && (v[adj] & 1) == (v[node] & 1)) isAble = 0;

• v[adj] : 이미 방문을 한적이 있는데
• (v[adj] & 1) == (v[node] & 1) : 현재 노드와 인접한 노드가 같은 그룹이라면 isAble = 0;

 

💙 Step 3 : 모든 정점에 대하여 검사 

 for(int i=1;i<=vertex;i++){
    if(v[i]) continue;
    // BFS 수행

• 그래프가 연결되지 않을 수도 있으므로, 모든 정점에서 BFS 시도
• 이미 방문한 정점은 건너뛰기

 

---

✅ 최종 코드 

// Depth를 이용한 방식(Depth가 홀수면 1번 그룹, 짝수면 0번 그룹)
#include<iostream>
#include<vector>
#include<queue>
# define MAX 20'001
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int t; cin>>t;
    while(t--){
        int vertex,e,isAble=1; cin>>vertex>>e; //그래프의 정점의 개수 V, 간선의 개수 E
        vector<vector<int>> graph(vertex+1);

        // 간선 입력 받기 
        for(int i=0,a,b;i<e;i++){
            cin>>a>>b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        //BFS
        queue<int> q; 
        int v[MAX]={0,};
        
        for(int i=1;i<=vertex;i++){
            if(v[i]) continue;

            q.push(i); v[i]=1;
            while(q.size()){
                int node = q.front(); q.pop();
                for(int adj : graph[node]){
                    // 같은 그룹에 있으면 NO
                    if(v[adj] && (v[adj]&1) == (v[node]&1)){ isAble=0; break;} 
                    // 아직 방문 안했으면 큐에 추가 
                    if(!v[adj]){ q.push(adj); v[adj]=v[node]+1; }
                }
                if(!isAble) break;
            }
        }

        if(isAble) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
}

 

 

---

🏃‍♀️ 다른 코드

• unionFind로 같은 그룹에 있는지 확인할 수도 있다. 

 

 

---

✨ 요약

알고리즘	BFS
핵심 아이디어	depth로 홀짝 구분해서 그룹 나누기
포인트	visit 배열 하나만 사용해서 그룹 체크!