3108번: 로고

(5, 5) ~ (8, 8)인 직사각형과 (6, 6) ~ (7, 7)인 직사각형이 있을 때 붙어있는지 구분하기가 힘들다.

그래서 각 좌표값에 *2를 해서 문제를 풀기 수월하도록 만들었다.

답을 구하기 위해서 DFS를 이용해 겹쳐진 직사각형이 몇개인지 구하고,

기준 좌표에 직사각형이 존재한다면 -1을 해서 답을 도출해냈다.

#include <iostream>
 
typedef struct {
    int y, x;
} dif;
 
dif dir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
 
int map[2001][2001] = { 0 };
int check[2001][2001] = { 0 };
 
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = *a;
}
 
void DFS(int y, int x) {
    if (check[y][x]) { return; }
    check[y][x] = 1;
 
    for (int i = 0; i < 4; i++) {
        int tempY = y + dir[i].y;
        int tempX = x + dir[i].x;
        if (tempY < 0 || tempY >= 2001 || tempX < 0 || tempX >= 2001) { continue; }
        if (!map[tempY][tempX]) { continue; }
        DFS(tempY, tempX);
    }
}
 
int main(void) {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    
    int N;
    std::cin >> N;
    int x1, y1, x2, y2;
    for (int i = 0; i < N; i++) {
        std::cin >> x1 >> y1 >> x2 >> y2;
        x1 = (x1 + 500) * 2;
        y1 = (y1 + 500) * 2;
        x2 = (x2 + 500) * 2;
        y2 = (y2 + 500) * 2;
 
        if (x2 < x1) {
            swap(&x1, &x2);
        }
        for (int k = x1; k <= x2; k++) {
            map[k][y1] = 1;
            map[k][y2] = 1;
        }
        if (y2 < y1) {
            swap(&y1, &y2);
        }
        for (int k = y1; k <= y2; k++) {
            map[x1][k] = 1;
            map[x2][k] = 1;
        }
    }
    
    int count = 0;
    for (int i = 0; i < 2001; i++) {
        for (int j = 0; j < 2001; j++) {
            if (!map[i][j] || check[i][j]) { continue; }
            DFS(i, j);
            count++;
        }
    }
    if (map[1000][1000]) { count--; }
 
    std::cout << count;
    return 0;
}