[백준] 1707: 이분 그래프 (C++)

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

 

문제

---

이분 그래프란?

그래프 이론에서 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

 

쉽게 말해서 어느 정점을 선택했을 때 간선을 통해 어디로 가든 RBRBRB...로 반복되어야 한다. (RED, BLUE)

 

이것을 풀어서 생각하면 두 집합으로 나눌 수 있는 그래프를 말한다.

 

즉 왼쪽이 있는 그래프를 모양만 좀 다르게 위치를 옮겨주면 오른쪽 그림이나 사실 똑같은 건데,

 

이런식으로 오른쪽 그림으로 만든 후 선 그어서 두 집합으로 나뉘어지면 그게 이분 그래프다.

 

아이디어

---

BFS, DFS 방식으로 모두 풀이가 가능하다.

 

나는 DFS 방식을 사용했다.

 

Code

---

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

#define RED 1
#define BLACK 2

vector<vector<int>> graph;
vector<int> visit;
bool bipartite;

void DFS(int node, int color) {
    visit[node] = color;
    // graph[node]: node에 대한 인접 정점들의 리스트를 모두 순회
    for (int next : graph[node]) {
        if (visit[next] == 0) {
            DFS(next, 3 - color);  // 3-color로 반대 색을 계산
        // 인접한 정점들이랑 지금 정점이랑 같은 색이면 안됌.
        } else if (visit[next] == color) {
            bipartite = false;
            return;
        }
    }
}

void init() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main() {
    init();

    int K;
    cin >> K;
    while (K--) {
        int V, E;
        cin >> V >> E;

        graph.assign(V + 1, vector<int>());
        visit.assign(V + 1, 0);
        bipartite = true;

        for (int i = 0; i < E; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        for (int i = 1; i <= V; i++) {
            if (visit[i] == 0) {
                DFS(i, RED);
                if (!bipartite) break;
            }
        }

        bipartite ? cout << "YES\n" : cout << "NO\n";
    }
    return 0;
}

 

초기화

        graph.assign(V + 1, vector<int>());
        visit.assign(V + 1, 0);
        bipartite = true;

메모리 절약을 위해 vector를 사용하여 동적으로 바꿨다.

정점 V는 1부터 시작이니 V+1만큼 0으로 모두 초기화 해주었다.

 

그래프 저장

        for (int i = 0; i < E; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

그래프의 정보를 저장해주었다.

 

예제를 변형해서 예를 들면

| 1 2
| 2 3
| 3 4
| 4 2

| 4 3

를 입력할 때 

각 정점에 인접하고 있는 정점 정보를 리스트형식으로 넣어준다.

graph[1] = {2}

graph[2] = {3}

graph[3] = {4}

graph[4] = {2,3}

 

DFS

void DFS(int node, int color) {
    visit[node] = color;
    // graph[node]: node에 대한 인접 정점들의 리스트를 모두 순회
    for (int next : graph[node]) {
        if (visit[next] == 0) {
            DFS(next, 3 - color);  // 3-color로 반대 색을 계산
        // 인접한 정점들이랑 지금 정점이랑 같은 색이면 안됌.
        } else if (visit[next] == color) {
            bipartite = false;
            return;
        }
    }
}

visit을 통해 각 정점(node)에 색을 저장한다. 0이 아니면 방문한 것을 알 수 있기때문에 굳이 1로 하지 않아도 된다.

 

해당 정점에 저장되어있는 인접 노드를 모두 방문한다.

 

만약 위 예시에서

graph[4] = {2,3} 처럼 인접노드가 2와 3인경우 graph[2], graph[3]을 방문한 곳이 아니라면

다시 DFS를 통해 색을 반전시켜주어 입력한다.

 

그런데 만약 인접한 부분이 방문되어 있는데 지금 정점노드랑 색이 같은 경우 이는 이분 그래프가 아니기 때문에 함수를 리턴해준다.

 

모든 정점을 선택했을 때 이분 그래프인지 검사

        for (int i = 1; i <= V; i++) {
            if (visit[i] == 0) {
                DFS(i, RED);
                if (!bipartite) break;
            }
        }

이제 주어진 V보다 작은 정점을 모두 DFS로 검사한다.

 

정점 1에서 시작했을 때 이분 그래프인데 정점 2에서 이분 그래프가 아닐 수 있다.

 

왜냐하면 정점끼리의 연결이 띄어져 있어 서로 다른 집합처럼 독립적으로 존재할 수도 있기 때문이다.

위와 같은 반례를 설명할 수 있다. 맨 위 첫 번째 파랑노드만 골랐을 때 인접한 정점이 하나기 때문에 이분 그래프를 만족한다.

 

하지만 두 번째 파랑노드는 세 번째 파랑노드와 연결되어 있다.