백준, BOJ, 1707번, 이분 그래프 : C++ [CPP] ★

 

사실 처음 들었을 때 이분그래프의 정의가 알아듣기 힘들었다.

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

??음.. 무슨 말이지??

즉, 나는 내 집합의 정점과 연결되면 안된다...? 

그렇다.

그냥 색을 2가지로 칠할 수 있을 때

인접한 노드가 나와 같은 색을 가지면 안된다는 말과 같다.

 

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

 

---

 

#맞은 풀이

#include <iostream>
#include <vector>

#define X first
#define Y second

#define MAX 20001

using namespace std;


int K; // 테스트케이스 수
int V, E; //정점, 간선 수

int node[MAX]; //이분그래프 -> 1이 red, 2 blue
// int adj[20001][20001];// 인접행렬 -> 하니까 메모리 초과 ★★★★★★★★★

vector <int> adj[MAX]; //벡터를 담는 배열 생성


bool isTrue = true; // 이분그래프인지



void dfs(int cur, int prevColor){
    //색칠안했으면 색칠해줌
    if(node[cur] == 0){
            node[cur] = (prevColor)%2 + 1; // 1이면 2가 2이면 1이됨
    }
    //이미 색칠했으면 색 비교
    else if(node[cur] != 0){
        //만약 인접한 노드가 같은색이면 false
        if(node[cur] == prevColor){isTrue = false; return;}
        //같은 색만 아니면 그냥 종료
        else{
            return;
        }
    }
    //해당 노드와 인접한 노드가 없으면 바로 종료
    if(adj[cur].empty()) return;
    
    
    //다음 방문할 노드 -> 
    for(auto x : adj[cur]){
        dfs(x, node[cur]); //이어진 노드(to) prevColor는 현재 노드의색
    }

    return;
}


int main(){
    cin >> K;

    while(K--){

        cin >> V >> E;
        
        //쓴 값들 초기화해야함
        for(int i = 0; i<= V; i++){
            adj[i].clear(); //해당 adj 벡터 초기화
            node[i] = 0; //해당 노드 초기화
        }
        isTrue = true;
        
        //시작
        
        for(int i = 0; i<E; i++){
            int from, to;
            cin >> from >> to;
            adj[from].push_back(to);
            adj[to].push_back(from); // 양방향 그래프이기 때문
        }
        
        //모든 노드에 대해서
        for(int i = 1; i<=V; i++){
            if(node[i] != 0)continue;//이미 색칠한 노드는 제외
            dfs(i, 1); //처음 시작하는 root노드는 이전컬러가 1(red) 로 시작
        }
        
        if(isTrue){
            cout << "YES" << '\n';
        }else{
            cout << "NO" << '\n';
        }
        

        
    }
    
    
    return 0;
}

 

 

나는 DFS로 색칠해가며 풀었다.

무조건 모든 노드에 대해서 색칠이 되었는지 확인해보아야 하고

색칠하지 않았다면 우선 해당 노드에 대해 DFS를 해봐야 한다.

 

조금 오래걸렸지만 메모리초과가 나서

인접행렬을 벡터로 바꾼 것 빼고

검색 없이 풀긴했다.

 

당연히 메모리초과가 날 것이라 예상했지만.. 

다시 말하지만

노드가 만 개가 넘어가면 인접행렬보다

벡터를 행렬로 만들어서 조금이라도 메모리를 줄여보자