[알고리즘 문제] 백준 1707번 이분 그래프

1707번: 이분 그래프 (acmicpc.net)

1707번: 이분 그래프

 

문제

 주어진 그래프에서 정점을 두 집합으로 분리하되, 두 집합 사이에 인접한 점이 없도록 하는 문제입니다.

 

아이디어

 두 집합 사이에 인접한 점이 없다는 말은, 인접한 두 점은 다른 집합이라는 뜻입니다.

 이를 통해 각 정점의 집합을 골라가며 그래프를 탐색하면 해결할 수 있습니다.

 여기서는 BFS를 사용해보겠습니다.

 

 1. 시작점을 임의의 집합으로 정하고 탐색을 시작합니다.

 

 

 2. 자신과 인접한 점은 다른 집합으로 표시합니다.

 

 3. 탐색 중 이미 표시한 점을 만났을 때, 자신과 다르다면 정상이니 넘어갑니다.

 

 4. 집합이 충돌한다면 이분 그래프로 표현할 수 없습니다.

 

 5. 탐색 완료 후, 탐색하지 않은 점이 있다면 1부터 다시 시작합니다. 

 

코드

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

int main() {
    int K;
    cin >> K;

    for (int i = 0; i < K; i++) {
        int V, E;
        cin >> V >> E;
        vector<vector<int>> graph(V);
        vector<bool> area(V);
        vector<bool> visit(V);
        queue<int> q;
        bool condition = true;

        // init graph
        for (int j = 0; j < E; j++) {
            int a, b;
            cin >> a >> b;
            graph[a-1].push_back(b-1);
            graph[b-1].push_back(a-1);
        }

        // BFS
        for (int j = 0; j < V; j++) {
            if (visit[j] == false) {
                area[j] = false;
                q.push(j);
                while (!q.empty()) {
                    int here = q.front(); q.pop();
                    for (size_t k = 0; k < graph[here].size(); k++) {
                        if (visit[graph[here][k]] == true) {
                            // violation detected
                            if (area[graph[here][k]] == area[here]) {
                                condition = false;
                                goto EXIT;
                            }
                        }
                        else {
                            area[graph[here][k]] = !area[here];
                            visit[graph[here][k]] = true;
                            q.push(graph[here][k]);
                        }
                    }
                }
            }
        }
        EXIT:;

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

 

기타

 이 문제를 DFS로 풀면 어떻게 될까요?

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

bool DFS(int idx, const vector<vector<int>> &graph, vector<bool> &area, vector<bool> &visit) {
    for (size_t i = 0; i < graph[idx].size(); i++) {
        if (visit[graph[idx][i]] == true) {
            if (area[graph[idx][i]] == area[idx]) {
                return false;
            }
        }
        else {
            visit[graph[idx][i]] = true;
            area[graph[idx][i]] = !area[idx];
            bool result = DFS(graph[idx][i], graph, area, visit);
            if (result == false)
                return false;
        }
    }
    return true;
}

int main() {
    int K;
    cin >> K;

    for (int i = 0; i < K; i++) {
        int V, E;
        cin >> V >> E;
        vector<vector<int>> graph(V);
        vector<bool> area(V);
        vector<bool> visit(V);
        bool condition = true;

        // init graph
        for (int j = 0; j < E; j++) {
            int a, b;
            cin >> a >> b;
            graph[a-1].push_back(b-1);
            graph[b-1].push_back(a-1);
        }

        // DFS
        for (int j = 0; j < V; j++) {
            if (visit[j] == false) {
                visit[j] = true;
                area[j] = false;
                bool result = DFS(j, graph, area, visit);
                if (result == false) {
                    condition = false;
                    break;
                }
            }
        }

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

 

 DFS와 BFS는 노드를 순회하는 순서 차이만 존재하고, 인접한 노드를 탐색한다는 점은 같기에 같은 아이디어로 해결할 수 있습니다.