[백준] 이분 그래프 1707 (Gold 4) - C++

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

 

문제를 처음 보고 한 착각

처음 이 문제를 접근했을 때는

이분 그래프가 정확히 뭔지 몰라서 연결 요소의 숫자를 구했었다.

로직은 맞는데 정답이 이상하게 나와 이상하다고 여겨

이분 그래프가 정확히 뭔지 구글링을 했다....

 

구글링을 한 결과 문제를 완전히 잘못 이해했다는 것을 깨달았다.

 

이분 그래프란 :

모든 정점을 두 개의 그룹으로 나누었을 때,
같은 그룹에 속한 정점끼리는 서로 연결된 간선이 없느 그래프
즉, 한 정점이 그룹 A라면 그 이웃들은 전부 그룹 B여야 한다. 

개념만 이해하고 나니까, 로직은 오히려 단순했다.

• 정점을 두 그룹으로 나눌 수 있는가?
• 모든 간선이 서로 다른 그룹을 연결하는가?

이 규칙만 지키면 이분 그래프다.

 

구현 아이디어

핵심 아이디어는 이거다.

• 하나의 visited 배열로 그룹 정보까지 같이 관리하자
• 방문 안 함: 0
• 그룹 A: 1
• 그룹 B: -1

이렇게 하면,

• 현재 정점이 1이면
• 이웃 정점은 무조건 -1이어야 한다.

부호만 반전시키면 그룹을 표현할 수 있어서 깔끔하다.

BFS로 검사하기

그래프가 연결 그래프라는 보장이 없기 때문에, 모든 정점에 대해 검사해야 한다.

그래서 전체 로직은 다음과 같다.

1. 모든 정점을 순회
2. 아직 방문하지 않은 정점이면
   • 해당 정점을 1 그룹으로 시작
   • BFS 시작
3. BFS 중에
   • 이웃이 아직 방문 안 됐으면 → 다른 그룹으로 지정
   • 이웃이 이미 방문됐는데 같은 그룹이면 → 이분 그래프 ❌

중요한 포인트는 이거다.

어떤 정점을 1로 시작하든, -1로 시작하든 상관없다.

어차피 이전에 방문되지 않았다면,
그 정점은 기존 탐색과 연결되지 않은 새로운 컴포넌트이기 때문이다.

최종 코드

#include <bits/stdc++.h>

using namespace std;

int main(){

    int k; //테스트 케이스 개수
    int v, e; // 정점, 간선

    cin>>k;
    for(int j=0;j<k;j++){
        cin>>v>>e;
        vector<vector<int>> graph(v);  //0-based
        for(int i=0;i<e;i++){// E개의 간선
            int a,b;
            cin>>a>>b;
            graph[a-1].push_back(b-1); //0-based
            graph[b-1].push_back(a-1);
        }

        //이분 그래프 : 
        //모든 정점을 두 개의 그룹으로 나누었을 때, 같은 그룹에 속한 정점끼리는 서로 연결된 간선이 없는 그래프
        //한 정점이 그룹 a일때 그 이웃들은 다 b여야 함.

        vector<int> visited(v,0); //visited 배열  -1이 unvisited;
        bool result=true;
        //visited 배열 1, -1 로 두 그룹을 표현하겠음
        for(int i=0;i<v;i++){//모든 정점을 검사
            if(visited[i]!=0) continue; // 이미 방문 pass
            if(!result) break;
            queue<int> q;
            q.push(i);
            int group= 1; // -로 두 그룹 구분
            visited[i]=group; // 첫 기준이 되는 정점은 1로 시작 
            // 왜 1,-1를 track 안해되 되는가 -> 만약 저번 탐색에서 visited이 아니라면 이미 서로 connected이 아님
            //기준이 되는 정점들 이웃 탐색해서 이웃과 다르게 세팅함
            while(!q.empty()){
                if(!result) break; 
                int t= q.front();
                group=visited[t]; 
                q.pop();
                for(auto a : graph[t]){
                    if(visited[a]== -group) continue; // 이미 방문했고 다른 group에 속한 이웃임
                    if(visited[a]==group) {
                        //이웃이 현재 정점과 같은 그룹임 -> false;
                        result=false;
                        break; //만약 함수로 짰다면 바로 return 해버려서 더 효율적이었을 듯
                    }
                    q.push(a);
                    visited[a]=-group; //다른 그룹임을 설정
                }
            }
        }
        
        if(result) cout<<"YES\n";
        else cout<<"NO\n";


    }

}

 

아쉬운 점

지금 코드에서는

• flag 변수
• break로 탈출 조건 처리

이런 식으로 early termination을 했다.

솔직히 말하면,

함수로 분리해서 return false 했으면
코드가 훨씬 깔끔했을 것 같다.

귀찮아서 한 번에 짜다 보니 이렇게 됐다.

시간 복잡도

• 각 정점은 최대 한 번 방문
• 각 간선은 최대 두 번 검사

따라서 전체 시간 복잡도는 O( V+E)