백준 9001 자바 - Rectangle Coloring (BOJ 9001 JAVA)

문제 : boj9001

 

1.

  우선 그룹의 개수는 어떻게 구할 수 있을까? 그룹 구하는데 특화된 union-find (분리 집합) 알고리즘을 사용하면 쉽게 그룹이 총 몇개인지 알 수 있다.

 

2.

  그럼 입력받은 직사각형들에 대해 모든 경우를 다 보면서 O(N*N) 서로 직사각형이 겹치는지 여부만 알 수 있다면 union-find로 그룹으로 만들어주고, 최종적으로 그룹의 개수를 출력해주면 된다. 직사각형 겹치는걸 확인하는데 가장 쉬운 방법은 배열에 직접 직사각형에 포함된 면적을 기입하면서 겹치는지 확인하는 것인데, 문제는 이 경우 최대 O(N*10000*10000) 이 걸리므로 불가하다. N이 최대 200인것에 착안해 좌표 압축을 통해 해봐도 된다. 그럼 최대 O(N^3)이면 구해볼 수 있다.

 

  내 경우엔 그냥 겹치는 모든 경우를 확인해보는 방식으로 진행했다.

직사각형 A와 B가 있다고 보자.

 

2.1 A의 4개의 꼭지점 중 하나가 B에 포함된다면 쉽게 겹치는지 알 수 있다.

 

2.2 '2.1'에 포함안된 경우는 A안에 B가 들어간 경우이다.

 

2.3 마지막으로 위의 과정으로 파악할 수 없는 경우는 다음의 경우이다.

 

이러한 경우들을 코드로 체크해주면서 union-find로 그루핑 한 후 그룹의 개수를 출력해주면 된다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;

class Rectangle {
    int x1, y1, x2, y2;
    public Rectangle(int x1, int y1, int x2, int y2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }
    public boolean contain(Rectangle rec) {
        int tmpX = this.x1;
        int tmpY = this.y1;
        if (rec.x1 <= tmpX && tmpX <= rec.x2 && rec.y1 <= tmpY && tmpY <= rec.y2) return true;
        tmpY = this.y2;
        if (rec.x1 <= tmpX && tmpX <= rec.x2 && rec.y1 <= tmpY && tmpY <= rec.y2) return true;
        tmpX = this.x2;
        if (rec.x1 <= tmpX && tmpX <= rec.x2 && rec.y1 <= tmpY && tmpY <= rec.y2) return true;
        tmpY = this.y1;
        if (rec.x1 <= tmpX && tmpX <= rec.x2 && rec.y1 <= tmpY && tmpY <= rec.y2) return true;

        tmpX = rec.x1;
        tmpY = rec.y1;
        if (x1 <= tmpX && tmpX <= x2 && y1 <= tmpY && tmpY <= y2) return true;

        if (rec.x1 <= x1 && x1 <= rec.x2 && y1 <= rec.y1 && rec.y2 <= y2) return true;
        if (x1 <= rec.x1 && rec.x1 <= x2 && rec.y1 <= y1 && y2 <= rec.y2) return true;
        if (rec.y1 <= y1 && y1 <= rec.y2 && x1 <= rec.x1 && rec.x2 <= x2) return true;
        if (y1 <= rec.y1 && rec.y1 <= y2 && rec.x1 <= x1 && x2 <= rec.x2) return true;

        return false;
    }
}

public class Main extends FastInput {
    private int[] parents;

    private int find(int a) {
        if (parents[a] < 0) return a;
        return parents[a] = find(parents[a]);
    }

    private void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        int h = parents[a]<parents[b] ? a:b;
        int l = parents[a]<parents[b] ? b:a;
        parents[a] += parents[b];
        parents[b] = a;
    }

    private void solution() throws Exception {
        int t = nextInt();
        StringBuilder answer = new StringBuilder();
        while (t-->0) {
            int n = nextInt();
            parents = new int[n];
            Arrays.fill(parents, -1);

            ArrayList<Rectangle> arr = new ArrayList<>(n);
            int arrIdx = 0;
            while (n-->0) {
                Rectangle cur = new Rectangle(nextInt(), nextInt(), nextInt(), nextInt());
                for (int i = 0; i < arr.size(); i++) {
                    if (arr.get(i).contain(cur)) {
                        union(i, arr.size());
                    }
                }
                arr.add(cur);
                arrIdx++;
            }

            int cnt = 0;
            for (int i = 0; i < parents.length; i++) {
                find(i);
                if (parents[i] < 0) cnt++;
            }
            answer.append(cnt).append('\n');
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}