코드 복사/붙여넣기 하는 당신이 아름답습니다.

3108 : 로고

풀이

사각형을 하나의 노드로 보자.

어떤 두 사각형 a, b가 겹친다면 두 사각형은 연결된 것으로 생각하자.

연결된 사각형들은 연필을 들지 않고 삥삥 돌며 잘 그릴 수 있다.

연필은 연결 요소의 개수 - 1번 들어주면 된다.

단, 시작점인 (0, 0)을 지나는 경우의 예외처리를 잘 해주자.

(x1=0, y1=0, x2=0, y2=0)인 경우도 비교해주면 된다.

Flood fill로 풀어도 된다.

코드

#include <cstdio>
#include <algorithm>
#define y1 fu
using namespace std;

const int n_ = 1000 + 1;

int n, x1[n_], y1[n_], x2[n_], y2[n_], pnt[n_], unq[n_];

int find(int u) {
    if (u == pnt[u]) return u;
    return pnt[u] = find(pnt[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u > v) swap(u, v);
    pnt[u] = v;
}

inline bool isout(int i, int j) {
    if (x1[i] > x1[j]) swap(i, j);
    if (x2[i] < x1[j] || y1[i] > y2[j] || y2[i] < y1[j]) return 1;
    if (x1[i] < x1[j] && x2[j] < x2[i] &&
        y1[i] < y1[j] && y2[j] < y2[i]) return 1;
    return 0;
}

int main() {
    int i, j;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
        pnt[i] = i;
    } pnt[n] = n;

    for (i = 0; i < n; i++) for (j = 1; j < n + 1; j++)
        if (!isout(i, j)) merge(i, j);

    int ans = 0;
    for (i = 0; i < n + 1; i++) unq[find(i)] = 1;
    for (i = 0; i < n + 1; i++) if (unq[i]) ans++;

    printf("%d", ans - 1);

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-04-06 19:10

Read more posts by this author