(2024-11-05) 1 문제 : 백준 - 1707 (이분 그래프)

 

이전에 풀었던 적의 적 문제와 완전히 동일한 문제였다. 첫 노드를 시작으로 주변의 노드를 체크하며 BFS로 탐색한다.

첫 노드를 1로 체크했다면 주변의 노드를 -1로 체크하고 현재 노드가 -1이라면 주변의 노드를 1로 만들며 이동한다.

그러다가 만약 현재 노드와 주변의 노드의 숫자가 동일한 상황이 발견된다면 이분 그래프가 될 수 없는 상태이므로 NO를 출력하면 된다.

 

그런데 문제가 그래프라고 해서 당연히 모든 정점이 이어져있을 줄 알았는데 그렇지 않았다.

입력으로 주어진 정점을 이어보면 두개이상의 그래프가 주어지는 입력도 있기 때문에 모든 노드에 대해 체크할 수 있도록 BFS를 반복적으로 돌아야 한다. 

 

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

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumCase = 0;
    std::cin >> NumCase;

    for (int Case = 0; Case < NumCase; Case++)
    {
        int NumNode = 0, NumEdge = 0;
        std::cin >> NumNode >> NumEdge;

        std::vector<std::vector<int>> Link(NumNode);
        std::vector<int> GroupTypes(NumNode);
        std::vector<bool> IsVisit(NumNode);

        for (int i = 0; i < NumEdge; i++)
        {
            int Start = 0, End = 0;
            std::cin >> Start >> End;

            Link[Start - 1].push_back(End - 1);
            Link[End - 1].push_back(Start - 1);
        }

        bool IsBG = true;

        while (true)
        {
            auto Iter = std::find(IsVisit.begin(), IsVisit.end(), false);

            if (Iter == IsVisit.end())
            {
                break;
            }

            int Index = Iter - IsVisit.begin();

            std::queue<int> BFS;
            BFS.push(Index);

            IsVisit[Index] = true;
            GroupTypes[Index] = 1;

            while (BFS.size() > 0)
            {
                int CurNode = BFS.front();
                BFS.pop();

                for (int i = 0; i < Link[CurNode].size(); i++)
                {
                    int NextNode = Link[CurNode][i];

                    if (GroupTypes[NextNode] == GroupTypes[CurNode])
                    {
                        IsBG = false;
                        break;
                    }

                    if (IsVisit[NextNode] == false)
                    {
                        GroupTypes[NextNode] = -GroupTypes[CurNode];
                        IsVisit[NextNode] = true;
                        BFS.push(NextNode);
                    }
                }
            }
        }

        (IsBG == true) ? std::cout << "YES\n" : std::cout << "NO\n";
    }

    return 0;
}