BOJ 3108 로고

로고

(http://boj.kr/3108)

완전 탐색 문제라는 걸 알고 봤는데도 뭘 기준으로 탐색을 해야하는지 찾기 힘들었다.

이 문제는 격자에서 구역을 나누는 것 처럼(Flood Fill) 교차되는 사각형끼리 이동하며 생기는 구역의 개수를 찾는 문제였다.

사각형이 교차하는지 판단하는 방법은 여러가지가 있겠지만,

사각형이 겹치면서 하나가 다른 하나를 완전히 포함하지 않는지를 확인했다.

Flood Fill이나 BFS를 배울 때 안전 영역같은 문제만 있는 건 아니라고 알려주기 좋은 문제같다.

#include <bits/stdc++.h>
 
using namespace std;
 
int ax[1001], ay[1001], bx[1001], by[1001];
bool chk[1001];
 
int main() {
    int n, i, j, cnt = 0;
 
    scanf("%d", &n);
 
    for (i = 0;i < n;++i)
        scanf("%d %d %d %d", &ax[i], &ay[i], &bx[i], &by[i]);
 
    queue<int> q;
 
    for (j = 0;j <= n;++j)
        if (chk[j] == false) {
            cnt++;
            q.push(j);
            chk[j] = true;
 
            while (!q.empty()) {
                int now = q.front();
                q.pop();
 
                for (i = 1;i <= n;++i) {
                    int tax = max(ax[now], ax[i]), tay = max(ay[now], ay[i]), tbx = min(bx[now], bx[i]), tby = min(by[now], by[i]);
 
                    if (tax > tbx || tay > tby || chk[i] == true || (ax[i] < ax[now] && ay[i] < ay[now] && bx[i] > bx[now] && by[i] > by[now]) || (ax[i] > ax[now] && ay[i] > ay[now] && bx[i] < bx[now] && by[i] < by[now]))
                        continue;
 
                    q.push(i);
                    chk[i] = true;
                }
            }
        }
 
    printf("%d", cnt - 1);
 
    return 0;
}