백준 g4 1707 이분 그래프 c++

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

1707번: 이분 그래프

 

문제

K개의 테스트 케이스가 주어진다.

각 테스트 케이스에서 V, E와 E개의 간선이 주어진다.

 

해당 그래프가 이분 그래프 인지 아닌지를 출력하기

*이분 그래프: 정점들을 두 집합으로 나눴을 때, 집합 내의 원소들끼리는 인접하지 않는 그래프

 

풀이

서로 인접한 노드들은 다른 집합에 속해야 한다.

노드들을 집합 A, 집합 B로 나눈다고 했을 때 vis에는 1, -1 으로 표시한다.

 

인접한 노드들을 만났을 때, vis가 0이면 방문하면 되고

vis가 -를 곱해준 수(1 -> -1, -1 -> 1)면 pass하면 되고

vis가 같은 수면 return false하면 된다. (인접한 노드들끼리 같은 집합에 있을 수 밖에 없다는 뜻이므로)

 

각 테스트케이스마다 adj, vis 모두 초기화 해줘야 한다.

 

전체 코드

/*boj g4 1701 이분 그래프*/
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 20002
using namespace std;

int K, V, E;
vector<int> adj[MAXN];
int vis[MAXN]; // 집합 A와 집합 B를 각각 1, -1로 표시

void initialize() {
    for (int i = 0; i < MAXN; i++) {
        adj[i].clear();
        vis[i] = 0;
    }
}

bool solve() {
    queue<int> Q;

    for (int s = 1; s <= V; s++) {
        if (vis[s]) continue;
        Q.push(s);
        vis[s] = 1;

        while (!Q.empty()) {
            int cur = Q.front();
            Q.pop();

            for (int a : adj[cur]) {
                if (vis[a] == vis[cur]) { // 인접한 곳이 같은 집합에 속하는 경우
                    return false;
                }
                if (vis[a] == -vis[cur]) { // 인접한 곳이 다른 집합에 속하는 경우
                    continue;
                }

                Q.push(a);
                vis[a] = -vis[cur];
            }
        }
    }

    return true;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> K;
    while (K--) {
        cin >> V >> E;
        initialize();
        for (int i = 0; i < E; i++) {
            int x, y;
            cin >> x >> y;

            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        bool result = solve();
        if (result)
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
    }
}

 

---

폐기된 풀이

 

처음에는 임의의 노드를 A집합에 넣고, A 집합에 넣을 수 있는 지 없는 지를 판단하며 greedy로 풀어보려고 했다.

if A에 들어갈 수 있으면 -> A 넣기
else B에 넣기

이런 식으로 진행하려고 했는데, 이때 A에 들어갈 수 있어도 A 말고 B에 들어가야 가능해지는 경우가 있는지에 대해 생각해보게 되었다.

 

만약 A에 들어갈 수 있는데도 B에 들어가야만 하는 노드를 마지막 점이라고 가정하면 이 경우는 A에 넣든 B에 넣든 상관이 없다. 왜냐하면 B에 마지막 점이 들어가든 말든 B끼리는 어차피 인접하지 않기 때문이다. 그래서 A에 들어가야하는 데도 B에 들어가야만 가능한 경우는 없다.

 

그러나 마지막 점이 아니라면, 넣을 당시엔 A에 들어갈 수 있었지만 결과적으로 마지막에는 A에 속하지 않아야 할 수도 있다. 조건 자체가 달라지므로 이 그리디 풀이는 폐기했다.