이 글에서는 파이썬을 이용해 두 개의 직사각형이 서로 겹치는지(overlap) 판별하는 알고리즘과 구현 방법을 살펴보겠습니다.
문제 정의
직사각형은 네 개의 요소를 가진 리스트 [x1, y1, x2, y2]로 표현합니다. 여기서 (x1, y1)은 왼쪽 아래(bottom-left) 모서리의 좌표이고, (x2, y2)는 오른쪽 위(top-right) 모서리의 좌표입니다.
두 직사각형이 겹친다는 것은 두 직사각형의 교집합 영역의 면적이 양수일 때를 의미합니다. 따라서 모서리의 꼭짓점 한 점에서만 맞닿거나, 변끼리만 접하는 경우에는 겹치는 것으로 간주하지 않습니다.
예를 들어 R1 = [0,0,2,2], R2 = [1,1,3,3]처럼 입력이 주어지면 두 직사각형이 실제로 면적을 가진 영역에서 서로 포개지므로 결과는 True가 됩니다.
해결 접근 방법
두 직사각형이 겹치지 않는 경우는 다음 네 가지 중 하나에 해당할 때입니다.
- R1이 R2보다 완전히 왼쪽에 있는 경우: R1[0] >= R2[2]
- R1이 R2보다 완전히 오른쪽에 있는 경우: R1[2] <= R2[0]
- R1이 R2보다 완전히 아래에 있는 경우: R1[1] >= R2[3]
- R1이 R2보다 완전히 위에 있는 경우: R1[3] <= R2[1]
위 조건 중 하나라도 참이라면 두 직사각형은 겹치지 않으므로 False를 반환하고, 그렇지 않다면 겹치는 것으로 판단하여 True를 반환하면 됩니다. 이 방식은 분리 축(separating axis) 아이디어를 활용한 것으로, 시간 복잡도는 O(1)로 매우 효율적입니다.
구현 예제
class Solution:
def solve(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.solve([0,0,3,3],[1,1,4,4]))
입력
[0,0,3,3], [1,1,4,4]
출력
True
위 코드에서 R1은 좌표 범위 (0,0)~(3,3), R2는 (1,1)~(4,4)이므로 두 직사각형은 x축 방향으로 1~3 구간에서, y축 방향으로도 1~3 구간에서 서로 겹칩니다. 교집합 영역인 (1,1)~(3,3)의 면적은 4로 양수이기 때문에 최종적으로 True가 출력됩니다.