백준 문제풀이 : (1707) 이분 그래프 - C/C++

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

1707번: 이분 그래프

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	256 MB	Gold 4	그래프,

 

 

문제

 

 

풀이

이분 그래프인지 판별하려면 시작 노드를 하나 정하고, 근처 노드를 지나가며 두 가지 색을 차례대로 칠해나가면 된다. 그 과정을 반복하다보면 마지막 노드에 도착할 때까지 무탈한 그래프가 있고, 중간에 같은 색을 칠해야하는 모순이 발생하는 그래프가 있다.

 

모순이 발생하지 않고 무사히 순회가 종료된다면 그 그래프는 이분그래프라고 볼 수 있다.

 

입력값을 인접리스트로 만들어 bfs를 수행할 수 있게 하고, 검정색과 하양색을 순회하며 번갈아 칠해 확인했다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include <deque>
#include <cstring>

using namespace std;
vector<vector<int>> graph;
int check[20001];

bool bfs(int node, int v) {
    deque<int> dq;
    dq.push_back(node);
    check[node]=-1; //시작은 검정
    
    while(!dq.empty()) {
        int cnode = dq[0];
        dq.pop_front();
        int pColor=check[cnode];
        
        for (int i=0 ; i<graph[cnode].size() ; i++) {
            int ckNode = graph[cnode][i];
            if (check[ckNode]==0) { //미방문 노드이면
                check[ckNode] = (pColor==-1) ? 1 : -1; //이전 노드와 다른 색으로 색칠
                dq.push_back(ckNode); //큐에 추가
            } else { //방문 노드라면
                if (pColor==check[ckNode]) { //색 배치에 모순 없는지 확인
                    return false; //모순이 있으면 bfs 종료. 이분 그래프 X
                }
            }
        }
    }
    
    return true;
}

int main() {
    int K;
    scanf("%d", &K);
    
    for (int k=0 ; k<K ; k++) {
        int V, E;
        scanf("%d %d", &V, &E);

        graph.resize(V+1);
        for (int i=0 ; i<=V ; i++) {
            graph[i].resize(0);
        }
        
        memset(check, 0, sizeof(int)*(V+1)); 
        //0 : 미방문, -1 : 검정 / 1 : 하양
        
        for (int e=0 ; e<E ; e++) {
            int node1, node2;
            scanf("%d %d", &node1, &node2);
            graph[node1].push_back(node2);
            graph[node2].push_back(node1);
        }
        
        bool result=true;
        for (int v=1 ; v<=V ; v++) {
            if (check[v]==0) result = bfs(v, V);
            if (!result) break;
        }
        
        
        printf("%s\n", result ? "YES" : "NO");

    }
}

 

 

END