[C++ / 백준 1707번] 이분 그래프

문제

 

 

 

시행 착오

인접 정점을 어떻게 해야 번갈아 가며 색으로 칠할 수 있는 지 고민했다.

 

 

 

해결 방법

삼항연산자로 간편하게 인접 정점에 부모 노드와 다른 색을 칠할 수 있었다..

 

예시 :

void DFS(int node, int c) {
    color[node] = c;
    visited[node] = true;

    for (auto v : g[node]) {
        if (color[v] == 0) { // 방문 안 한 경우
            DFS(v, c == RED ? BLUE : RED);
        }
    }
}

 

 

 

 

 

DFS 사용해서 해결

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

#define RED 1
#define BLUE 2

using namespace std;

int K, V, E;

vector<int> g[20001];
bool visited[20001];
int color[20001];

bool check(int node) {
    visited[node] = true;
    
    for (auto v : g[node]) {
        if (color[v] == color[node]) { // 인접 노드와 색이 같으면 이분 그래프 아님
            return false;
        }
        if (!visited[v]) {
            if (!check(v)) return false;
        }
    }
    return true;
}

void DFS(int node, int c) {
    color[node] = c;
    visited[node] = true;

    for (auto v : g[node]) {
        if (color[v] == 0) { // 방문 안 한 경우
            DFS(v, c == RED ? BLUE : RED);
        }
    }
}

int main() {
    cin >> K;

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

        for (int i = 1; i <= V; i++) {
            g[i].clear();
            visited[i] = false;
            color[i] = 0;
        }

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

        // DFS로 색칠하기
        for (int i = 1; i <= V; i++) {
            if (color[i] == 0) {
                DFS(i, RED);
            }
        }

        // 이분 그래프 판별
        fill(visited, visited + V + 1, false);
        bool isbi = true;
        for (int i = 1; i <= V; i++) {
            if (!visited[i]) {
                if (!check(i)) {
                    isbi = false;
                    break;
                }
            }
        }

        cout << (isbi ? "YES\n" : "NO\n");
    }

    return 0;
}

 

BFS 사용해 구현

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

#define RED 1
#define BLUE 2

using namespace std;

int K, V, E;

vector<int> g[20001];
bool visited[20001];
int color[20001];


bool BFS(int node) {
    queue<int> q;
    q.push(node);
    color[node] = RED; // 처음 시작은 RED
 
    while (!q.empty()) {
        int next = q.front();
        q.pop();

        for (auto i : g[next]) {
            if (color[i] == 0) {
                color[i] = (color[next] == RED ? BLUE : RED);
                 q.push(i);
            }
            else if (color[i] == color[next]) { // 같은 색이면 이분 그래프 아님
                return false;
            }
        }
    }
    return true;
}


int main() {
    cin >> K;

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

        for (int i = 1; i <= V; i++) {
            g[i].clear();
            visited[i] = false;
            color[i] = 0;
        }

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


        bool isbi = true;

        for (int i = 1; i <= V; i++)
        {
            if (color[i] == 0)
                if (!BFS(i))
                {
                    isbi = false;
                    break;
                }
        }
        


        cout << (isbi ? "YES\n" : "NO\n");
    }

    return 0;
}