BOJ 3108번 로고

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

github : https://github.com/junho0956/Algorithm/blob/master/3108/3108/%EC%86%8C%EC%8A%A4.cpp

 

이 문제를 푸는 요령은 2가지가 있습니다.

 

1) BFS 또는 DFS 를 이용해서 한붓그리기를 코드

2) 애초에 사각형이 겹치는 부분에 대한 탐색을 하면되니 DFS 를 이용한 사각형의 겹침 부분을 코드

 

1번으로 풀다가 틀려서 2번으로 방법을 변경하였습니다.

check_box() 에 대해서 설명해보자면

check_box() 는 사각형이 겹치는지 안겹치는지 판단하는 함수로,

false 를 반환할 때 겹친다라고 가정하였습니다.

 

lx[a] < fx[b] || ly[a] < fy[b] 의 부분은 두 사각형이 아예 떨어져있는 경우로

true 를 반환하게 되어, 사각형이 겹치지 않는다를 의미하게 됩니다.

fx[a] > fx[b] && lx[a] < lx[b] && fy[a] > fy[b] && ly[a] < ly[b] 의 부분은

한 사각형이 다른 사각형을 포함하고 있음을 나타내는 경우로

true 를 반환하게 되어, 사각형이 겹치지 않는다를 의미하게 됩니다.

 

둘다 만족하지 않아 false 를 반환하게 되는 경우는 무조건 사각형이 겹치게 됨을 의미하게 되어,

다른 사각형을 확인하게 되는 dfs() 로 진입하게 됩니다.

 

문제의 중요한 부분은 (0,0) 부터 탐색을 시작해야한다는 것이고,

이를 위해서 반복문을 0<=N 으로 작성하였습니다.

일부러 cin >> +1 해가면서 좌표를 받은 이유도 첫 좌표는 (0,0),(0,0) 이라는 점(사각형이 됩니다)을 사용하기

위해서 입니다.

 

마지막에 ans-1 의 -1 을 해준 이유 역시 반복문은 최소 1번이상 실행되게 되어있는데

(0,0) 에 걸치는 사각형이 존재할 수 있기 때문입니다.

 

#include <iostream>
using namespace std;
#pragma warning(disable:4996)
 
int N;
int fy[1001], fx[1001], lx[1001], ly[1001];
bool visit[1001];
 
bool check_box(int a, int b) {
    return (lx[a] < fx[b] || ly[a] < fy[b] || fx[a] > fx[b] && lx[a] < lx[b] && fy[a] > fy[b] && ly[a] < ly[b]);
}
 
void dfs(int now) {
 
    visit[now] = true;
    for (int i = 0; i <= N; i++) {
        if (visit[i]) continue;
        if (!check_box(now,i) && !check_box(i,now)) {
            dfs(i);
        }
    }
 
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    bool temp = false;
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> fx[i+1] >> fy[i+1] >> lx[i+1] >> ly[i+1];
    }
 
    int ans = 0;
    
    for (int i = 0; i <= N; i++) {
        if (visit[i]) continue;
        ans++;
        dfs(i);
    }
 
    cout << ans - 1;
    return 0;
}