백준 3108 로고

문제 링크

연필을 몇번 떼어야 하는가를 구하는 문제이다.
이는 총 몇개의 집합인지를 구해야 하는 문제로 치환된다.

집합의 수를 구한다 -> union-find로 푼다.

1. 어떤 사각형을 맞닿아있다고 판단할 지

bool isConnect(int i, int j){
    Info a = infos[i];
    Info b = infos[j];
    
	if (b.y2 > a.y2 && a.x2 < b.x2 && a.y1 > b.y1 && b.x1 < a.x1)
		return false;
	if (a.y2 > b.y2 && b.x2 < a.x2 && b.y1 > a.y1 && b.x1 > a.x1)
		return false;
	if (b.y1 > a.y2 || b.x1 > a.x2 || a.y1 > b.y2 || b.x2 < a.x1)
		return false;
	return true;
}

위 2 조건은 B가 A를 완전히 포함하는 경우 / A가 B를 완전히 포함하는 경우

3번째 조건은 다음과 같이 만나지 않는 경우이다.

원점을 포함하는 사각형이 있는지

bool containOrigin(Info a){
    return (a.x1 == 0 && a.y1 * a.y2 <= 0 ) || (a.x2 == 0 && a.y1 * a.y2 <= 0 ) || 
            (a.y1 == 0 && a.x1 * a.x2 <= 0 ) || (a.y2 == 0 && a.x1 * a.x2 <= 0 ); 
}

원점을 포함하는 사각형이 없다면 처음에 무조건 펜을 떼야하기에 펜을 한번 들어야 한다.

전체 코드는 다음과 같다.

#include<iostream>

using namespace std;

struct Info {
    int x1, y1, x2, y2;

    Info(){}
    Info(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2){}
};

int parent[1000];
Info infos[1000];
int N;
bool rootVisited[1000];

int getParent(int a){
    if(parent[a] == a) return a;
    return parent[a] = getParent(parent[a]);
}

void unionGroup(int a, int b){
    a = getParent(a);
    b = getParent(b);

    if(a == b) return;
    parent[a] = b;
}

bool isConnect(int i, int j){
    Info a = infos[i];
    Info b = infos[j];
    
	if (b.y2 > a.y2 && a.x2 < b.x2 && a.y1 > b.y1 && b.x1 < a.x1)
		return false;
	if (a.y2 > b.y2 && b.x2 < a.x2 && b.y1 > a.y1 && b.x1 > a.x1)
		return false;
	if (b.y1 > a.y2 || b.x1 > a.x2 || a.y1 > b.y2 || b.x2 < a.x1)
		return false;
	return true;
}

bool containOrigin(Info a){
    return (a.x1 == 0 && a.y1 * a.y2 <= 0 ) || (a.x2 == 0 && a.y1 * a.y2 <= 0 ) || 
            (a.y1 == 0 && a.x1 * a.x2 <= 0 ) || (a.y2 == 0 && a.x1 * a.x2 <= 0 ); 
}

int main(){
    cin >> N;
    for(int i = 0; i < N;i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        infos[i] = Info(x1, y1, x2, y2);
    }

    for(int i = 0; i < N;i++) parent[i] = i;
    
    for(int i = 0 ; i <= N-2;i++){
        for(int j = i + 1; j <= N-1;j++){
            if(isConnect(i, j)) {
                unionGroup(i, j);
            }
        }
    }

    // 몇 덩어리인지 
    int cnt = -1;
    for(int i = 0; i < N;i++){
        // cout << getParent(i) << endl;
        if(!rootVisited[getParent(i)]){
            cnt++;
            rootVisited[getParent(i)] = true;
        }
    }

    // (0,0)을 포함하는지 
    bool flag = false;
    for(int i = 0; i < N;i++){
        if(containOrigin(infos[i])){
            flag = true;
            break;
        }
    }
    if(!flag) cnt++;
    cout << cnt << endl;
    return 0;
}