어느 게임 개발자의 기록

BFS를 통해 경우의 수를 모두 탐색하면 된다. 다만, 각 좌표의 방문체크를 1번만 해도 지나갈 수 없게 된다면 정답을 구할 수가 없게 된다. 그러므로 방문체크 배열을 [K + 1][Height ][Width] 의 크기를 가진 3차원 배열로 선언하여 사용해야 한다.

BFS를 할 때마다, 현재 남은 말 이동 횟수를 카운팅하며 해당 카운팅과 동일한 카운팅을 가진 상태로 다음 좌표에 진입한 적이 있는지를 체크하는 것이다.

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

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

int main()
{
    Init();

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

    int Width = 0, Height = 0;
    std::cin >> Width >> Height;

    std::vector<std::vector<int>> Board(Height, std::vector<int>(Width));
    for (int i = 0; i < Height; i++)
    {
        for (int j = 0; j < Width; j++)
        {
            std::cin >> Board[i][j];
        }
    }

    std::vector<std::vector<std::vector<bool>>> IsVisit(31, std::vector<std::vector<bool>>(Height, std::vector<bool>(Width)));
    IsVisit[0][0][0] = true;

    std::queue<std::tuple<int, int, int, int>> BFS;
    BFS.push({ 0, 0, 0, HorseCount });

    std::vector<int> DirX = { 0, 1, 0, -1 };
    std::vector<int> DirY = { 1, 0, -1, 0 };

    std::vector<int> HorseDirX = { -2, -2, -1, -1, 1, 1, 2, 2 };
    std::vector<int> HorseDirY = { -1, 1, -2, 2, -2, 2, -1, 1 };

    int Answer = INT_MAX;

    while (BFS.size() > 0)
    {
        auto [CurY, CurX, MoveCount, CurHorseCount] = BFS.front();
        BFS.pop();

        if (CurY == Height - 1 && CurX == Width - 1)
        {
            Answer = std::min(Answer, MoveCount);
            continue;
        }

        for (int i = 0; i < 4; i++)
        {
            int NextX = CurX + DirX[i];
            int NextY = CurY + DirY[i];

            if (NextX < 0 || NextY < 0 || NextX >= Width || NextY >= Height)
            {
                continue;
            }

            if (IsVisit[CurHorseCount][NextY][NextX] == true)
            {
                continue;
            }

            if (Board[NextY][NextX] == 1)
            {
                continue;
            }

            IsVisit[CurHorseCount][NextY][NextX] = true;
            BFS.push({ NextY, NextX, MoveCount + 1, CurHorseCount });
        }

        if (CurHorseCount == 0)
        {
            continue;
        }

        for (int i = 0; i < 8; i++)
        {
            int NextX = CurX + HorseDirX[i];
            int NextY = CurY + HorseDirY[i];

            if (NextX < 0 || NextY < 0 || NextX >= Width || NextY >= Height)
            {
                continue;
            }

            if (IsVisit[CurHorseCount - 1][NextY][NextX] == true)
            {
                continue;
            }

            if (Board[NextY][NextX] == 1)
            {
                continue;
            }

            IsVisit[CurHorseCount - 1][NextY][NextX] = true;
            BFS.push({ NextY, NextX, MoveCount + 1, CurHorseCount - 1 });
        }
    }

    if (Answer == INT_MAX)
    {
        Answer = -1;
    }

    std::cout << Answer;
    return 0;
}

BFS나 DFS 아무거나 써도 되는 최단거리 찾기 문제이다.

다만 사각형을 움직였을 때, 사각형의 변이 위치하는 좌표에 장애물이 존재하지 않는지 모두 확인해주어야 한다. 

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

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

int main()
{
    Init();

    int Height = 0, Width = 0;
    std::cin >> Height >> Width;

    std::vector<std::vector<int>> Board(Height, std::vector<int>(Width));
    for (int i = 0; i < Height; i++)
    {
        for (int j = 0; j < Width; j++)
        {
            std::cin >> Board[i][j];
        }
    }

    std::pair<int, int> RectSize, StartPos, EndPos;
    std::cin >> RectSize.first >> RectSize.second >> StartPos.first >> StartPos.second >> EndPos.first >> EndPos.second;
    StartPos.first--, StartPos.second--, EndPos.first--, EndPos.second--;

    std::queue<std::tuple<std::pair<int, int>, int>> BFS;
    BFS.push({ StartPos, 0 });

    std::vector<std::vector<bool>> IsVisit(Height, std::vector<bool>(Width));
    IsVisit[StartPos.first][StartPos.second] = true;

    std::vector<int> DirX = { 1, -1, 0, 0};
    std::vector<int> DirY = { 0, 0, 1, -1};

    std::vector<int> CheckX = { RectSize.second, -1, 0, 0 };
    std::vector<int> CheckY = { 0, 0, RectSize.first, -1 };

    while (BFS.size() > 0)
    {
        auto [CurPos, MoveCount] = BFS.front();
        BFS.pop();

        if (CurPos == EndPos)
        {
            std::cout << MoveCount;
            return 0;
        }

        for (int i = 0; i < 4; i++)
        {
            int NextX = CurPos.second + DirX[i];
            int NextY = CurPos.first + DirY[i];

            if (NextX < 0 || NextY < 0 || NextX > Width - RectSize.second || NextY > Height - RectSize.first)
            {
                continue;
            }

            if (IsVisit[NextY][NextX] == true)
            {
                continue;
            }

            bool CanGo = true;

            for (int j = 0; j < RectSize.first; j++)
            {
                if (Board[CurPos.first + j][CurPos.second + CheckX[i]] == 1)
                {
                    CanGo = false;
                    break;
                }
            }

            for (int j = 0; j < RectSize.second; j++)
            {
                if (Board[CurPos.first + CheckY[i]][CurPos.second + j] == 1)
                {
                    CanGo = false;
                    break;
                }
            }

            if (CanGo == true)
            {
                IsVisit[NextY][NextX] = true;
                BFS.push({ {NextY, NextX}, MoveCount + 1 });
            }
        }
    }

    std::cout << -1;

    return 0;
}

플로이드-워셜 알고리즘을 통해 모든 노드간의 최단거리를 구한 뒤에 사이클의 거리(i ->j + j -> i)의 최소값을 구하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

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

int main()
{
    Init();

    int NumCity = 0, NumEdge = 0;
    std::cin >> NumCity >> NumEdge;

    std::vector<std::vector<int>> MinDist(NumCity, std::vector<int>(NumCity, 999999999));
    for (int i = 0; i < NumCity; i++)
    {
        MinDist[i][i] = 0;
    }

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

        MinDist[Start][End] = Cost;
    }

    for (int i = 0; i < NumCity; i++)
    {
        for (int j = 0; j < NumCity; j++)
        {
            for (int k = 0; k < NumCity; k++)
            {
                MinDist[j][k] = std::min(MinDist[j][k], MinDist[j][i] + MinDist[i][k]);
            }
        }
    }

    int MinCycle = INT_MAX;

    for (int i = 0; i < NumCity; i++)
    {
        for (int j = i + 1; j < NumCity; j++)
        {
            if (MinDist[i][j] != 999999999 && MinDist[j][i] != 999999999)
            {
                MinCycle = std::min(MinCycle, MinDist[i][j] + MinDist[j][i]);
            }
        }
    }

    if (MinCycle == INT_MAX)
    {
        MinCycle = -1;
    }

    std::cout << MinCycle;

    return 0;
}

간단한 BFS 문제이다. Queue를 통해 가능한 모든 경우를 탐색하면 된다.

주의해야 할 점은 세 가지 정도 있다.

1. long long 타입을 써야한다. (오버플로우 주의)

2. 방문체크해야됨 (중복을 방지하지 않으면 무한루프 발생. 본인은 unordered_set으로 방문체크 했다.)

3. 아스키 코드 순서에 맞게 Queue에 다음 원소를 삽입해야 함. ('*' -> '+' -> '-' -> '/' )

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

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

int main()
{
    Init();

    int StartNumber = 0, TargetNumber = 0;
    std::cin >> StartNumber >> TargetNumber;

    std::queue<std::pair<long long, std::string>> Queue;
    Queue.push({ StartNumber, "" });

    std::unordered_set<long long> Check;

    while (Queue.size() > 0)
    {
        auto [CurNumber, CurSigns] = Queue.front();
        Queue.pop();

        if (CurNumber == TargetNumber)
        {
            if (CurSigns == "")
            {
                std::cout << 0;
                return 0;
            }

            std::cout << CurSigns;
            return 0;
        }

        long long MulValue = CurNumber * CurNumber;
        if (Check.find(MulValue) == Check.end())
        {
            Check.insert(MulValue);
            Queue.push({ MulValue, CurSigns + "*" });
        }

        long long AddValue = CurNumber + CurNumber;
        if (Check.find(AddValue) == Check.end())
        {
            Check.insert(AddValue);
            Queue.push({ AddValue, CurSigns + "+" });
        }

        long long SubValue = CurNumber - CurNumber;
        if (Check.find(SubValue) == Check.end())
        {
            Check.insert(SubValue);
            Queue.push({ SubValue, CurSigns + "-" });
        }
        
        if (CurNumber != 0)
        {
            long long DivValue = CurNumber / CurNumber;

            if (Check.find(DivValue) == Check.end())
            {
                Check.insert(DivValue);
                Queue.push({ DivValue, CurSigns + "/" });
            }
        }
    }

    std::cout << -1;

    return 0;
}

스택을 사용하는 문제이다. 연산자 간의 우선순위를 따져서 출력하는 로직을 짜면 된다.

본인이 출력한 로직은 아래와 같다. 먼저, 모든 연산 기호는 stack에 삽입해주었다. 

1. 알파벳이라면 그대로 정답 문자열의 맨 뒤에 문자를 삽입해준다.

2. 현재 문자가 ')' 이라면 연산 기호 스택의 top이 '(' 이 될 때까지 계속 기호를 pop하며 문자의 맨 뒤에 삽입해준다.

3. 현재 기호가 ')'이 아니고 우선순위가 stack의 top의 우선순위와 같다면 정답 문자열의 맨 뒤에 이전 문자를 삽입한 뒤 stack을 pop한다. 현재 문자는 stack에 삽입해준다.

4. 현재 기호가 ')'이 아니고 우선순위가 이전 문자보다 낮다면 정답 문자열의 맨 뒤에 이전 문 문자를 삽입한 뒤 stack을 pop한다. 현재 문자는 stack에 삽입해준다.

5. 이외의 경우엔 stack에 기호를 삽입해준다.

#include <iostream>
#include <vector>

#include <queue>
#include <stack>

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

int main()
{
    Init();

    std::string Input;
    std::cin >> Input;

    std::stack<char> Sign;

    std::string Answer = "";

    for (int i = 0; i < Input.size(); i++)
    {
        char CurChar = Input[i];

        if (CurChar >= 'A' && CurChar <= 'Z')
        {
            Answer.push_back(CurChar);
        }
        else
        {
            if (CurChar == ')')
            {
                while (Sign.size() > 0 && Sign.top() != '(')
                {
                    Answer.push_back(Sign.top());
                    Sign.pop();
                }

                if (Sign.size() > 0 && Sign.top() == '(')
                {
                    Sign.pop();
                }
                
            else if (Sign.size() > 0 && (Sign.top() == '+' || Sign.top() == '-') && (CurChar == '+' || CurChar == '-'))
            {
                Answer.push_back(Sign.top());
                Sign.pop();
                Sign.push(CurChar);
            }
            else if (Sign.size() > 0 && (Sign.top() == '*' || Sign.top() == '/') && (CurChar == '*' || CurChar == '/'))
            {
                Answer.push_back(Sign.top());
                Sign.pop();
                Sign.push(CurChar);
            }
            else if (Sign.size() > 0 && (Sign.top() == '*' || Sign.top() == '/') && (CurChar == '+' || CurChar == '-'))
            {
                while (Sign.size() > 0 && Sign.top() != '(')
                {
                    Answer.push_back(Sign.top());
                    Sign.pop();
                }

                Sign.push(CurChar);
            }
            else
            {
                Sign.push(CurChar);
            }
        }
    }

    while(Sign.size() > 0)
    {
        Answer.push_back(Sign.top());
        Sign.pop();
    }

    std::cout << Answer;

    return 0;
}

겹치는 사각형들끼리 그룹을 만들어서 몇개의 그룹이 나오는지 구하는 문제이다.

(겹쳐있는 사각형들끼리는 한 번에 그릴 수 있으므로)

먼저, 사각형이 겹쳐있는지 판별해준다. AABB 충돌검사로 간단하게 해결할 수 있다. 하지만, 한 가지 예외가 있는데, 한 사각형이 다른 사각형의 내부에 완전히 포함되는 경우이다. 이 경우엔 펜을 올렸다가 다시 내려야 하기 때문에 이 경우는 제외해준다. 

DFS를 통해 충돌하는 사각형을 모두 그룹화해주면 된다. 그 이후 그룹의 개수를 출력하면 되는데 역시나 한가지 예외가 또 존재한다. 바로 시작점에서 바로 그림을 그릴 수 있는 경우이다. (시작할 땐 펜을 내린 상태로 시작하므로 PU없이 그림을 그릴 수 있다.)

그러므로 시작점에서 바로 그림을 그릴 수 있는 경우엔 그룹의 개수에서 1을 뺀 값을 출력해야 한다.

본인은 Left가 0이거나 Right가 0인 상황에서 사각형의 y2는 양수, 사각형의 y1은 음수인 경우 혹은 Top이나 Down이 0인 상황에서 Left가 음수거나 Right가 양수인 상황에 시작점에서 바로 그릴 수 있다고 판단하였다.

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

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

struct Rect
{
    int Left = 0;
    int Top = 0;
    
    int Right = 0;
    int Down = 0;
};

bool AABB(const Rect& _First, const Rect& _Second)
{
    return !(_First.Right < _Second.Left || _First.Left > _Second.Right || _First.Top > _Second.Down || _First.Down < _Second.Top);
}

bool IsInnerRect(const Rect& _First, const Rect& _Second)
{
    if (_First.Left < _Second.Left && _First.Right > _Second.Right && _First.Top < _Second.Top && _First.Down > _Second.Down)
    {
        return true;
    }

    if (_Second.Left < _First.Left && _Second.Right > _First.Right && _Second.Top < _First.Top && _Second.Down > _First.Down)
    {
        return true;
    }

    return false;
}

void DFS(const std::vector<Rect>& _Rects, std::vector<int>& _IsCheck, int _Index, int _Count)
{
    _IsCheck[_Index] = _Count;

    for (int i = 0; i < _Rects.size(); i++)
    {
        if (i == _Index)
        {
            continue;
        }

        if (_IsCheck[i] != -1)
        {
            continue;
        }

        if (AABB(_Rects[i], _Rects[_Index]) == true && IsInnerRect(_Rects[i], _Rects[_Index]) == false)
        {
            DFS(_Rects, _IsCheck, i, _Count);
        }
    }
}

int main()
{
    Init();

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

    std::vector<Rect> Rects(NumRect);
    for (int i = 0; i < NumRect; i++)
    {
    	std::cin >> Rects[i].Left >> Rects[i].Top >> Rects[i].Right >> Rects[i].Down;
    }

    int CollisionCount = 0;
    std::vector<int> CollisionOrder(NumRect, -1);

    while (true)
    {
        auto FindIter = std::find(CollisionOrder.begin(), CollisionOrder.end(), -1);

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

        int Index = FindIter - CollisionOrder.begin();

        DFS(Rects, CollisionOrder, Index, CollisionCount);
        CollisionCount++;
    }

    int Answer = CollisionCount;
    
    for (int i = 0; i < NumRect; i++)
    {
        if((Rects[i].Left == 0 || Rects[i].Right == 0) && (Rects[i].Top <= 0 && Rects[i].Down >= 0))
        {
            Answer--;
            break;
        }
        
        if ((Rects[i].Top == 0 || Rects[i].Down == 0) && (Rects[i].Left <= 0 && Rects[i].Right >= 0))
        {
            Answer--;
            break;
        }
    }

    std::cout << Answer;

    return 0;
}

문제가 뭔가 복잡해보이지만, 생각보단 단순한 문제이다. (비문학 문제..)

다익스트라를 통해 최단거리를 갱신하면서 최종적으로 해당 노드에 진입하는 간선을 저장해주면 되는 것이다. 문제는 결국 슈퍼컴퓨터에서 각 컴퓨터로 가는 최단거리를 구하고, 최단 경로에 해당하는 간선을 출력하는 문제이기 때문이다. 최단거리가 갱신될 때 간선도 함께 저장해주면 된다.

무슨말이냐면, 다익스트라를 통해 최단거리를 갱신할 때 2번 노드로 도착하는 간선이 처음엔 1->2번이었다면 2번 노드에 해당하는 간선을 {1, 2}로 저장하고, 나중에 3->2번 간선을 통해 2번 노드의 최단거리가 갱신되었다면 2번 노드에 해당하는 간선을 {3, 2}로 저장하면 된다.

그렇게 노드에 대한 간선을 모두 갱신한 뒤에 모두 출력해주면 된다.

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <map>

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

int main()
{
    Init();

    int NumComputer = 0, NumLine = 0;
    std::cin >> NumComputer >> NumLine;

    std::vector<std::vector<std::pair<int, int>>> Link(NumComputer);
    for (int i = 0; i < NumLine; i++)
    {
        int Start = 0, End = 0, Cost = 0;
        std::cin >> Start >> End >> Cost;

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

    std::vector<int> MinDist(NumComputer, INT_MAX);
    MinDist[0] = 0;

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> Dijk;
    Dijk.push({ 0, 0 });

    std::map<int, std::pair<int, int>> Answers;

    while (Dijk.size() > 0)
    {
        auto [CurNode, CurDist] = Dijk.top();
        Dijk.pop();

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

            if (MinDist[NextNode] > CurDist + Link[CurNode][i].second)
            {
                MinDist[NextNode] = CurDist + Link[CurNode][i].second;
                Answers[NextNode] = { CurNode, NextNode };

                Dijk.push({ NextNode, MinDist[NextNode] });
            }
        }
    }

    std::cout << Answers.size() << "\n";

    for (const auto& Pair : Answers)
    {
        std::cout << Pair.second.first + 1 << " " << Pair.second.second + 1 << "\n";
    }
    
    return 0;
}

빈칸을 앞에서부터 DFS로 채워나가면 된다. 빈칸의 좌표를 모두 벡터에 넣어두고 숫자를 1~9까지 하나씩 넣어보면서 현재 빈칸에 숫자를 넣을 수 있는지 체크한다. 만약 넣을 수 있다면 다음 빈칸에 대해 DFS를 수행한다.

계속 DFS를 수행하다가 모든 빈칸을 채우게 되면 보드의 숫자를 모두 출력하고 종료하면 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>

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

bool Check(std::vector<std::vector<int>>& _Board, const std::pair<int, int>& _CheckPos, int _CheckNum)
{
    //가로
    for (int i = 0; i < 9; i++)
    {
        if (_Board[_CheckPos.first][i] == _CheckNum)
        {
            return false;
        }
    }

    //세로
    for (int i = 0; i < 9; i++)
    {
        if (_Board[i][_CheckPos.second] == _CheckNum)
        {
            return false;
        }
    }

    //사각형
    int XStart = _CheckPos.second - (_CheckPos.second % 3);
    int YStart = _CheckPos.first - (_CheckPos.first % 3);

    for (int i = YStart; i < YStart + 3; i++)
    {
        for (int j = XStart; j < XStart + 3; j++)
        {
            if (_Board[i][j] == _CheckNum)
            {
                return false;
            }
        }
    }

    return true;
}

void DFS(std::vector<std::vector<int>>& _Board, std::vector<std::pair<int, int>>& _EmptyPos, int _CurIndex)
{
    if (_CurIndex == _EmptyPos.size())
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                std::cout << _Board[i][j] << " ";
            }

            std::cout << "\n";
        }

        exit(0);
        return;
    }

    auto [CurY, CurX] = _EmptyPos[_CurIndex];

    for (int i = 1; i <= 9; i++)
    {
        if (Check(_Board, _EmptyPos[_CurIndex], i) == true)
        {
            _Board[CurY][CurX] = i;
            DFS(_Board, _EmptyPos, _CurIndex + 1);
            _Board[CurY][CurX] = 0;
        }
    }
}

int main()
{
    Init();

    std::vector<std::vector<int>> Board(9, std::vector<int>(9));
    std::vector<std::pair<int, int>> EmptyPos;
    
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            std::cin >> Board[i][j];

            if (Board[i][j] == 0)
            {
                EmptyPos.push_back({i, j});
            }
        }
    }

    DFS(Board, EmptyPos, 0);

    return 0;
}

이전에 풀었던 적의 적 문제와 완전히 동일한 문제였다. 첫 노드를 시작으로 주변의 노드를 체크하며 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;
}

이 문제는 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;
}