백준 3108 - 로고

1. 문제 정리
  - 한붓그리기(해밀턴 경로)문제이다.

  - 명령어는 무시를 해도 좋다.

  - 거북이의 첫 좌표는 0,0 이며, 연필을 내려놓은 채로 시작한다.

  - 겹치는 직사각형을 하나로 간주하여, 해당 직사각형의 수의 최소값을 정답으로 한다.
 
2. 접근
  - 처음에는 bfs로 접근하여으나 직사각형이 겹치는 조건을 이용하여 문제를 해결하기로 하였다.

  - 직사각형이 서로 겹치지 않는 조건은, 서로 떨어져 있을 때(즉, 한 직사각형의 가장 큰 x좌표가 다른 직사각형의 가장 작은 x좌표 보다 작을 때 등)와 내포하고 있을 때(큰 직사각형이 작은 직사각형을 품고 있을 때)로 총 각 6가지가 된다.

  - 위 6가지 경우를 제외하고는 직사각형은 서로 겹치므로 겹친 직사각형에 하나의 번호를 배정해 하나의 연합으로 간주한다.

  - 연합의 수의 최소값을 반환하고자 한다.

3. 풀이

#include<iostream>
#include<vector>
#include<set>
using namespace std;

struct rec{
    int x1, y1, x2, y2;
}typedef rec;

int n;
int a[1000];
int par[1001];
vector<rec> rect;

int find_parent(int x){
    if(par[x] == x) return x;
    return par[x] = find_parent(par[x]);
}

void make_union(int a, int b){
    a = find_parent(a);
    b = find_parent(b);
    if(a < b) par[b] = a;
    else if(a > b) par[a] = b;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;

    rect.push_back({0, 0, 0, 0});
    for(int i = 0; i < n; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        rect.push_back({x1, y1, x2, y2});
    }

    for(int i = 0; i < 1000; i++) a[i] = -1;
    for(int i = 0; i <= n; i++) par[i] = i;

    for(int i = 0; i < n; i++){
        for(int j = i+1; j <= n; j++){
            if(rect[i].x1 > rect[j].x2) continue;
            if(rect[i].x2 < rect[j].x1) continue;
            if(rect[i].y1 > rect[j].y2) continue;
            if(rect[i].y2 < rect[j].y1) continue;
            if(rect[i].x1 < rect[j].x1 && rect[i].y1 < rect[j].y1 && rect[i].x2 > rect[j].x2 && rect[i].y2 > rect[j].y2) continue;
            if(rect[i].x1 > rect[j].x1 && rect[i].y1 > rect[j].y1 && rect[i].x2 < rect[j].x2 && rect[i].y2 < rect[j].y2) continue;
            else {
                make_union(i, j);
            }
        }
    }

    set<int> s;
    for(int i = 0; i <= n; i++) s.insert(find_parent(par[i]));
    cout << s.size()-1;
}

  - struct rec : 직사각형의 각각 x1, y1, x2, y2의 입력값을 저장할 구조체이다

  - int par[1001] : 인덱스가 일치하는 직사각형이 어떤 연합에 속해있는지(어떤 번호를 들고있는 지) 저장하는 배열이다.

  - int find_parent(int x) : x를 인덱스로 하는 직사각형의 연합 번호가 최소값을 가지도록 번호를 찾는 함수이다.

  - void make_union(int a, int b) : a, b 인덱스를 갖는 직사각형을 하나의 연합으로 묶고, 그 중 가장 작은 번호를 가진 연합에 포함시킨다.(par[a], par[b]의 값을 최소화한다.)

  - int main() : n, x1, y1, x2, y2값을 모두 입력 받고, 직사각형이 겹치는 경우에 한해 make_union을 호출한다. for loop가 끝난 뒤, par 배열에 저장된 모든 값을 set<int> s에 저장하고, set Container가 중복된 값을 저장하지 않는 것을 이용하여 연합의 수의 최소값을 출력하고 반환한다.
 
4. 소감

  처음에는 bfs를 통해 한분그리기 유형의 문제를 풀려고 했으나, 해당 문제가 직사각형만을 그릴 수 있는 점을 이용하여 직사각형이 겹치는 경우를 선별해 문제를 해결하고자 하였다. 처음에는 par[]을 사용하지 않고, 각 직사각형에 인덱싱을 하여 겹치는 직사각형의 수가 몇개인지  확인하려고 하였으나 해당 로직에 대해서는 문제가 풀리지 않았다.(예외 케이스는 다 통과해서 한참 걸렸던 것 같다.)

  이 상황에서는 재귀를 이용해야 한다.. 이 상황에서는 어떤 로직을 써야한다.. 라는 것이 아직 머리에 잡히지 않은 것 같아서 아쉬움을 많으 느꼈던 문제였다.