7/24 TIL : 완전탐색

어제 올리고자는걸 까먹어서,,,ㅋㅋㅋ 지금이라도 올려본당

오늘도 완전탐색을 열심히 풀어봤다!

근데 풀수록 이게 맞나 싶다.. 이렇게 for를 많이 중첩하는게 맞다고???..... 의문이 많이 생긴다.

 

이번에 좀 고심했던건 겹쳐지지 않는 두 직사각형에서

두 직사각형이 겹쳐지는지를 판별하는 부분이었다.

 

처음에는 if문으로 "겹쳐지는상황" 을 판별하여 골라내려고 했다.

근데 이 상황이 생각보다 너무 많은 경우의수가 발생하였다.

 

일단 이런식으로 겹쳐져있는 상황을 생각할 수 있다. 사각형의 한 꼭짓점이, 다른사각형의 내부에 있으면 반드시 겹쳐지게된다.

사각형 A, B라고 생각할때

1) A의 minx < B의 minx < A의 maxx

2) A miny < B miny < A maxy

1 && 2

3) A minx < B maxx < A maxx

4) A miny < B maxy < A maxy

3 && 4

... 이런식으로 모든 꼭짓점에 대해 포함관계를 조건으로 생각해볼 수 있다.

 

두번째로는 이런식으로 포함되어 있는 모양을 생각할 수 있다.

오른쪽 모양의 경우, 위에서 꼭짓점의 포함여부를 판별할 때 같이 걸러지지만

왼쪽 모양의 경우, 꼭짓점이 들어가있지 않아서 걸리지 않는다.

즉 이런 모양에 대해서도 추가적인 처리가 필요해진다.

=> 너무 조건이 복잡해짐!!

 

그래서 반대로 "겹쳐지지 않는 상황" 을 골라내고, 나머지를 전부 겹쳐지는 상황으로 처리하려고 해봤다.

이런식으로 빨간색 네모에 대해, 파란색 네모가 안겹쳐지는 상황들을 그려봤다.

공통점은?? 각 사각형의 x, y좌표의 min max비교만으로 처리가 가능해진다는 점이다!

1) A maxx < B minx : A보다 B가 오른쪽에 와있음

2) A minx > B maxx : A보다 B가 왼쪽에 있음

3) A maxy < B miny : A보다 B가 위에 있음

4) A miny > B many : A보다 B가 아래에 있음

이렇게 간단한 조건으로 처리가 가능해진다.

bool is_in(vector<int> left, vector<int> right, vector<int> left2, vector<int> right2){
    int x1min = left[0];
    int y1min = left[1];
    int x1max = right[0];
    int y1max = right[1];
    int x2min = left2[0];
    int y2min = left2[1];
    int x2max = right2[0];
    int y2max = right2[1];

    
    if(x1max < x2min || y1max < y2min){
        return true;
    }
    if(x2max < x1min || y2max < y1min){
        return true;
    }

    return false;
}

코드로 표현하면 이런형태가 된다.

 

---

옛날에 막 C언어 처음배울 때 이런 문제를 풀어본 기억이 있긴했는데,..

그 당시에는 꼭짓점의 포함여부로 판별했던것같다.

왜 풀렸는지는 의문이지만,,, 이번에 생각한 접근방법이 더 맞는것같다.