백준 3108번: 로고 (C++)

접근

https://www.acmicpc.net/problem/3108

3108번: 로고

처음에 문제를 볼 때부터 사각형끼리 연결될 경우 유니언하는 disjoint set(union-find) 방식 문제 풀이가 떠올랐다. 중간에 생각해보니 배열을 이용하여 사각형을 실제로 그리고 bfs를 통해 따로 떨어진 묶음들을 카운트하는 방법이 더 간단한 방법이었음을 깨달았지만 이미 너무 많이 지나쳐와서 disjoint set 알고리즘을 이용하여 문제 풀이 완료하였다.

두개의 사각형이 연결되는 방식은 매우 여러개지만, 두개의 사각형이 완전히 분리되는 방식은 한 사각형이 다른 사각형의 안에 완전히 들어가 있거나, 두 사각형이 완전히 상하좌우 방향으로 떨어진 경우만 생각해주면 된다. 이러한 경우에만 false를 리턴하는 isConnected 함수를 이용하여, 이 함수가 true를 리턴하면 두 사각형을 union하고, 마지막에는 각 사각형의 서로다른 parent의 수를 set을 이용하여 중복되지 않게 카운트해주었다.

코드

#include <iostream>
#include <set>

using namespace std;

#define endl '\n'
#define MAX_N 1001

struct RECTANGLE {
    int x1;
    int y1;
    int x2;
    int y2;
};

int N;
RECTANGLE Rectangle[MAX_N];
int parents[MAX_N];
int ranks[MAX_N];

int Find(int x) {
    if (parents[x] == x) {
        return x;
    } else {
        return parents[x] = Find(parents[x]);
    }
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    if (ranks[x] < ranks[y]) {
        parents[x] = y;
    } else {
        parents[y] = x;
        if (ranks[x] == ranks[y]) {
            ranks[x]++;
        }
    }
}

bool isConnected(RECTANGLE a, RECTANGLE b) {
    int ax1 = a.x1, ay1 = a.y1, ax2 = a.x2, ay2 = a.y2;
    int bx1 = b.x1, by1 = b.y1, bx2 = b.x2, by2 = b.y2;
    // b 사각형 안에 a 사각형이 완전히 들어가는 경우
    if (bx1 < ax1 && ax2 < bx2 && by1 < ay1 && ay2 < by2) return false;
    // a 사각형 안에 b 사각형이 완전히 들어가는 경우
    if (ax1 < bx1 && bx2 < ax2 && ay1 < by1 && by2 < ay2) return false;
    // 두 사각형이 외곽 방향으로 완전히 겹치지 않는 경우
    if (bx2 < ax1 || ax2 < bx1 || by2 < ay1 || ay2 < by1) return false;
    return true;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N;
    // 처음 위치에서 펜을 내리고 시작하므로 원점과 겹치는 사각형의 존재를 확인하기 위해 원점을 먼저 추가
    parents[0] = 0;
    ranks[0] = 0;
    Rectangle[0] = {0, 0, 0, 0};
    for (int i = 1; i <= N; i++) {
        parents[i] = i;
        ranks[i] = 0;
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        Rectangle[i] = {a, b, c, d};
    }
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j <= N; j++) {
            // 사각형끼리 연결되어있을 경우 유니언
            if (isConnected(Rectangle[i], Rectangle[j])) {
                Union(i, j);
            }
        }
    }
    set<int> ans;
    for (int i = 0; i <= N; i++) {
        ans.insert(Find(i));
    }
    cout << ans.size() - 1 << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!