(2024-11-05) 4 문제 : 백준 - 3108 (로고)

 

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

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

 

먼저, 사각형이 겹쳐있는지 판별해준다. 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;
}