[BOJ] #1707 이분 그래프

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

1707번: 이분 그래프

---

인접 리스트로 주어진 그래프를 보고 이분 그래프인지 아닌지 판별하면 된다. 이분 그래프에 대한 자세한 내용은 필자가 따로 정리해두었으니 해당 게시물 참조하면 된다. ⤵️

https://jhoon-study.tistory.com/89

[자료구조] 이분 그래프 Bipartite Graph

문제는 이 이분 그래프를 C++ 코드로 어떻게 옮기는가 인데..

코드의 전체적인 매커니즘은 다음과 같다. DFS와 BFS 방식 모두 사용가능 한데, 필자는 BFS 방식을 사용했다.

 

1. 인접 리스트 형태로 그래프를 입력 받는다.

2. BFS로 그래프를 탐색하며 맨 처음 방문하는 정점을 RED라 설정하고, 이후에 탐색하는 인접한 정점들은 BLUE로 설정한다. 이때, 필자는 visited배열에서 0은 아직 방문 안한 정점 / 1은 RED / 2는 BLUE로 가정하였다.

3. RED와 BLUE가 배정된 그래프를 가지고 isBipartite 함수로 이분 그래프인지 아닌지 판별한다. 인접한 정점들을 전부 탐색하며 현재 정점과 연결된 다른 정점의 색깔이 같을 경우 그 즉시 탐색을 종료하고 false를 return한다.

4. 모든 정점들을 다 탐색했을때 같은 색끼리 인접한것이 없다면 true를 return한다.

5. isBipartite 함수의 return 값에 따라 결과값을 적절히 출력하고, 다음 테스트 케이스를 위해 clear 함수로 Graph와 visited배열을 전부 초기화해준다.

 

이분 그래프를 판별하는 법은 생각보다 어려울것은 없지만, C++ 코드로 실제로 옮기는 과정이 좀 어려웠던 것 같다. BFS를 활용한 알고리즘 중에서 대표적인 방식이니 잘 기억해두도록 하자.

#include <iostream>
#include <queue>
#include <vector>

#define MAX 200001
#define RED 1
#define BLUE 2

using namespace std;

int V,E;
vector<int> Graph[MAX];
int visited[MAX] = { 0 };

void BFS(int start) {
    queue<int> Q;
    Q.push(start);
    visited[start] = RED;

    int color = RED;
    while (!Q.empty()) {
        int curr = Q.front();
        Q.pop();

        if (visited[curr] == RED) color = BLUE;
        else if (visited[curr] == BLUE) color = RED;

        for (int i=0; i<Graph[curr].size(); i++) {
            int idx = Graph[curr][i];

            if (!visited[idx]) {
                Q.push(idx);
                visited[idx] = color;
            }
        }
    }
}

bool isBipartite() {
    for (int curr=1; curr<=V; curr++) {
        for (int j=0; j<Graph[curr].size(); j++) {
            int next = Graph[curr][j];
            
            if (visited[curr] == visited[next]) return false;
        }
    }
    return true;
}

void clear() {
    for (int i=0; i<=V; i++) {
        Graph[i].clear();
        visited[i] = 0;
    }
}

int main() {
    cin.tie();
    cout.tie();
    ios::sync_with_stdio(false);

    int K;
    cin >> K;

    while (K-->0) {
        cin >> V >> E;

        for (int i=0; i<E; i++) {
            int a,b;
            cin >> a >> b;

            Graph[a].push_back(b);
            Graph[b].push_back(a);
        }

        for (int i=1; i<=V; i++) {
            if (!visited[i]) {
                BFS(i);
            }
        }

        isBipartite() ? cout << "YES" << '\n' : cout << "NO" << '\n';

        clear();
    }

    return 0;
}

마지막 clear 함수의 범위값을 잘못 설정해서 한번 틀렸다...