(2024-11-04) 3 문제 : 백준 - 12893 (적의 적)

 

이 문제는 BFS를 이용해 주변의 친구들을 적으로 만들면서 완전탐색하다가 만약 주위에 나와 같은 진영의 친구가 존재한다면 0을 출력하면 되는 문제이다. 이 개념 자체는 어렵지 않다.

 

다만, 한 가지 간과할 수가 있는 것이 모든 친구들이 연결되어 있지 않을 수 있다는 것이다.

예를 들어 적대관계가 1 2 / 2 3 / 4 5 / 5 6 으로 주어진다면 1번에서 시작한 한 번의 BFS로 1,2,3 은 탐색할 수 있지만 4,5,6은 탐색할 수가 없다.즉, 모든 관계를 다 확인할 때 까지 BFS를 반복적으로 돌려주어야 한다. 

 

본인은 isVisit라는 방문배열을 만들었고 해당 방문배열중 false인 원소를 찾아 해당 원소를 기준으로 BFS를 돌도록 하였다. 그리고 BFS가 끝나고나서 isVisit에서 다시 false인 원소를 찾고 만약 false인 원소가 없다면 그대로1 을 출력하고 종료하면 되고 false인 원소가 있다면 다시 BFS를 돌도록 하였다. 

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

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

int main()
{
    Init();

    int NumMan = 0, NumRelation = 0;
    std::cin >> NumMan >> NumRelation;

    std::vector<std::vector<int>> Link(NumMan);
    std::vector<int> Relation(NumMan);
    std::vector<bool> isVisit(NumMan);

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

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

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

        if (FindIter == isVisit.end())
        {
            break;
        }

        int Index = FindIter - isVisit.begin();

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

        isVisit[Index] = true;
        Relation[Index] = 1;

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

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

                if (Relation[NextNode] == Relation[CurIndex])
                {
                    std::cout << 0;
                    return 0;
                }

                if (isVisit[NextNode] == false)
                {
                    BFS.push(NextNode);
                    Relation[NextNode] = -Relation[CurIndex];
                    isVisit[NextNode] = true;
                }
            }
        }
    }

    std::cout << 1;

    return 0;
}