Python으로 두 사각형의 겹침 여부 확인하기

사각형은 리스트 [x1, y1, x2, y2]로 표현할 수 있습니다. 여기서 (x1, y1)은 사각형의 왼쪽 아래 꼭짓점 좌표이고, (x2, y2)는 오른쪽 위 꼭짓점 좌표입니다.

두 사각형이 '겹친다'는 것은 두 사각형의 교집합 영역(면적)이 양수일 때를 의미합니다. 따라서 모서리나 변만 맞닿아 있는 경우에는 겹침으로 판단하지 않습니다.

축에 평행한(axis-aligned) 두 개의 사각형이 주어졌을 때, 이 두 사각형이 서로 겹치는지 확인하는 것이 이 문제의 목표입니다.

예를 들어 입력이 다음과 같다면,

• R1 = [0,0,2,2]
• R2 = [1,1,3,3]

두 사각형은 영역을 공유하므로 출력은 True가 됩니다.

해결 접근 방법

두 사각형이 겹치지 않는 경우는 명확하게 구분할 수 있습니다. 한 사각형이 다른 사각형보다 완전히 왼쪽, 오른쪽, 위쪽 또는 아래쪽에 있는 경우입니다. 이 조건을 반대로 생각하면 해결 방법이 단순해집니다.

다음 단계로 문제를 해결할 수 있습니다:

• 다음 네 가지 조건 중 하나라도 참이면 두 사각형은 겹치지 않습니다:
  • R1[0] >= R2[2] → R1이 R2보다 완전히 오른쪽에 있거나 맞닿아 있는 경우
  • R1[2] <= R2[0] → R1이 R2보다 완전히 왼쪽에 있거나 맞닿아 있는 경우
  • R1[3] <= R2[1] → R1이 R2보다 완전히 아래에 있거나 맞닿아 있는 경우
  • R1[1] >= R2[3] → R1이 R2보다 완전히 위에 있거나 맞닿아 있는 경우
• 위 조건 중 하나라도 만족하면 False를 반환합니다.
• 그렇지 않으면 두 사각형은 겹치므로 True를 반환합니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

class Solution:
    def isRectangleOverlap(self, R1, R2):
        if (R1[0] >= R2[2]) or (R1[2] <= R2[0]) or (R1[3] <= R2[1]) or (R1[1] >= R2[3]):
            return False
        else:
            return True

ob = Solution()
print(ob.isRectangleOverlap([0,0,2,2],[1,1,3,3]))

입력

[0,0,2,2],[1,1,3,3]

출력

True

복잡도 분석

• 시간 복잡도: O(1) — 단순 비교 연산만 수행하므로 상수 시간에 처리됩니다.
• 공간 복잡도: O(1) — 추가 메모리가 필요하지 않습니다.

이 방법은 직관적이면서도 효율적으로 사각형 겹침 문제를 해결할 수 있는 대표적인 기법으로, 충돌 감지(collision detection), UI 요소 배치 검증 등 다양한 실무 상황에서 활용됩니다.