[백준 3108] 로고

문제

www.acmicpc.net/problem/3108

알고리즘

union find

풀이

좌표평면 위 사각형들이 주어졌을 때, (0,0)에서 시작하여 PU명령을 몇 번 해야 하는지 묻고 있습니다. 거북이는 (0,0)에 펜을 내리고 있는 상황입니다.

문제에서 주어진 예제를 그려본다면 (5,0) 과 (8,3)으로 이루어진 사각형을 제외하고는 모든 사각형이 이어져있음을 알 수 있습니다. PU명령이 필요할 때는 이어져 있지 않은 사각형을 그리러 갈 때입니다. 즉 사각형들이 이어져 있다면 하나의 그룹으로 카운트를 할 수 있는 유니온파인드를 사용합시다.

이중 포문을 통해 모든 사각형들이 겹치는지 안겹치는지를 확인하는 과정에서 겹친다면 유니온을 진행합니다. 유니온의 기준은 인덱스 번호가 큰 쪽으로 유니온을 진행합니다. 이유는 0~$N-1$인덱스는 문제에서 주어지는 사각형이고 $N$인덱스는 (0,0)을 의미합니다. (0,0)과 사각형이 겹치게 된다면 PU명령이 필요 없기 때문입니다. 마지막 포문에서 $N-1$까지만 $parent$를 검사함으로써 (0,0)과 겹치는 사각형과의 카운트를 피합니다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, ans;
int X1[1010], Y1[1010], X2[1010], Y2[1010];
int parent[1010];

int find(int x) {
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}

bool inr(int a, int b, int c, int d) {
    return a < c && d < b;
}

bool overlap(int i, int j) {
    //한쪽이 오른쪽에 있다
    if (X1[i] > X2[j] || X1[j] > X2[i]) return false;
    //한쪽이 위에있다
    if (Y1[i] > Y2[j] || Y1[j] > Y2[i]) return false;
    //한쪽이 다른쪽을 아에 포함한다
    if (inr(X1[i], X2[i], X1[j], X2[j]) && inr(Y1[i], Y2[i], Y1[j], Y2[j])) return false;
    if (inr(X1[j], X2[j], X1[i], X2[i]) && inr(Y1[j], Y2[j], Y1[i], Y2[i])) return false;
    return true;
}

int main() {
    FAST;
    memset(parent, -1, sizeof(parent));

    cin >> N;
    rep(i, N) cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];

    for (int i = 0;i < N;++i) for (int j = i + 1;j <= N;++j) {

        if (overlap(i, j)) {
            int a = find(i);
            int b = find(j);
            if (a > b) swap(a, b);
            if (a != b) parent[a] = b;
        }
    }

    for (int i = 0;i < N;++i) if (parent[i] < 0) ++ans;
    cout << ans;

    return 0;
}