[백준] 1707번: 이분 그래프 C++ - BFS, 큐를 사용하여 이분 그래프 판단하기.

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

 

문제를 좀 분석해 보자면 간선의 수는 200000, 정점의 수는 20000, 테스트 케이스 5개이다. 시간 복잡도는 꽤나 여유로워 보이니 문제를 분석해 보았다. 그래프를 두 집합으로 분할하되, 분할된 집합에서 인접하는 노드가 없게끔 분할하면 된다.

 

가장 먼저 떠오르는건 흐름은 다음과 같았다.

1. 시작점 start를 한 집합에 넣고, 인접한 점은 다른 집합에 넣는다.
2. 방문하지 않은 점 next에 대해 똑같이 1번을 수행한다.

이렇게 떠올랐는데 굉장히 큰 오류들이 있었다.

먼저 next는 첫 번째 단계의 start와 연관되어 있을 수 있었다. 즉, 맨 처음 시작점의 인접한 점과 그다음 방문하지 않은 점이 인접하다면? 인접하지 않다면? 모두 다른 방향으로 풀이를 진행해야 할 것이다. 따라서 그냥 순서대로 방문하는 게 아니라, bfs가 필요하다고 생각했다.

1. start에 대해 bfs를 수행하면서 집합을 나눈다. 이 과정에서 이분 그래프가 맞는지 아닌지 체크한다.
2. 그 다음 방문하지 않은 점은 start와는 전혀 무관한 그래프이다. 연결되어 있지 않으므로 1번과 똑같이 bfs를 하면서 집합을 나눌 수 있다.

bfs가 갑자기 왜 떠올랐을까? 이 부분이 좀 중요한 것 같은데, bfs가 필요한 상황을 외우는 게 아니다. 현재 시작점 start와 인접한 점들을 집합으로 나누어야 하는데, 한 번 인접한 게 아니라 두 번, 세 번 인접 즉 연결되어 있는 그래프를 한 번에 집합으로 나누어야 한다.

여기서 떠오른게 bfs인 것이다. start와 바로 인접한 점을 다른 집합에 넣고, 다음 bfs step에서 또 다른 집합(start와 같은 집합)에 넣고,... 이런 식으로 뭔가 퍼져나가듯이 집합을 나누고 이분 그래프인지 체크하고 이런 흐름에서 bfs를 포착한 것이고 더 정확히는 큐를 포착한 것이다!

너무 겁먹지 말고 차근 차근 떠올려보면 해결할 수 있다.

/** 그래프 1707 이분 그래프 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int K, v, e;
int group[20100];
vector<int> g[20100];

string solve()
{
    fill(group, group + v + 1, -1);

    // 첫 번째 점을 시작으로 인접한 점의 집합을 1로, 본인은 0으로 만든다.
    // 첫 번째 점과 인접한 점을 큐에 넣는다.
    // 큐에서 뺀 점에 대해 인접한 점의 집합을 0으로 만드는데, 1이 있으면 이분 그래프가 아닌 것이다.

    for (int i = 1; i <= v; i++)
    {
        if (group[i] != -1)
            continue;

        queue<int> q;
        q.push(i);
        group[i] = 0;

        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            for (auto next : g[cur])
            {
                if (group[next] != -1)
                {
                    if (group[next] == group[cur])
                        return "NO\n";
                    else
                        continue;
                }

                group[next] = 1 - group[cur];
                q.push(next);
            }
        }
    }
    return "YES\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> K;
    while (K--)
    {
        cin >> v >> e;
        for (int i = 1; i <= v; i++)
            g[i].clear();

        for (int i = 0; i < e; i++)
        {
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        cout << solve();
    }
}