[리트코드] 1401 - Circle and Rectangle Overlapping

1401. Circle and Rectangle Overlapping

Medium

---

You are given a circle represented as (radius, xCenter, yCenter) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return true if the circle and rectangle are overlapped otherwise return false. In other words, check if there is any point (xi, yi) that belongs to the circle and the rectangle at the same time.

 

Example 1:

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0).

Example 2:

Input: radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Example 3:

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

 

Constraints:

• 1 <= radius <= 2000
• -104 <= xCenter, yCenter <= 104
• -104 <= x1 < x2 <= 104
• -104 <= y1 < y2 <= 104

분류

수학, 기하학

---

문제 풀이

다음은 주어진 코드를 분석하고 문제 풀이 방법을 한국어로 자세히 설명합니다.

---

문제 분석

이 문제는 원과 축에 정렬된 직사각형이 겹치는지 여부를 판단하는 문제입니다.

• 입력:
  • radius (r): 원의 반지름.
  • xCenter, yCenter (x, y): 원의 중심 좌표.
  • x1, y1: 직사각형의 좌하단(bottom-left) 모서리 좌표.
  • x2, y2: 직사각형의 우상단(top-right) 모서리 좌표.
• 출력: 원과 직사각형이 하나라도 공통된 점을 가지면 true를, 그렇지 않으면 false를 반환합니다.
• 제약 조건: 모든 좌표와 반지름은 정수이며, 비교적 큰 범위(-10^4 ~ 10^4)를 가집니다. 반지름은 항상 양수입니다. x1 < x2, y1 < y2이므로 직사각형은 항상 유효합니다.

접근 방법

이 문제를 해결하는 핵심 아이디어는 "원의 중심에서 직사각형까지의 최단 거리"를 이용하는 것입니다. 원과 직사각형이 겹치려면, 원의 중심에서 직사각형의 경계 또는 내부의 어떤 점까지의 최단 거리가 원의 반지름보다 작거나 같아야 합니다. 만약 이 최단 거리가 반지름보다 크다면, 원은 직사각형과 떨어져 있는 것이므로 겹치지 않습니다.

따라서, 이 문제를 해결하기 위한 단계는 다음과 같습니다:

1. 원의 중심에서 직사각형에 가장 가까운 점 (cx, cy)을 찾습니다.
2. 원의 중심 (x, y)와 직사각형에 가장 가까운 점 (cx, cy) 사이의 거리를 계산합니다.
3. 계산된 거리가 원의 반지름 r보다 작거나 같은지 확인합니다.

이 접근 방식은 기하학적인 직관을 기반으로 하며, 간단한 산술 연산만으로 해결할 수 있어 효율적입니다.

구현 설명

주어진 파이썬 코드는 위에서 설명한 접근 방식을 정확하게 구현합니다.

1단계: 직사각형 내 가장 가까운 x-좌표 찾기

• cx = max(x1, min(x, x2))
• 이 단계에서는 원의 중심 x 좌표를 기준으로 직사각형 내에서 가장 가까운 x-좌표 cx를 결정합니다.
• min(x, x2)는 원의 중심 x와 직사각형의 우측 경계 x2 중 더 작은 값을 선택합니다. 이는 x가 x2보다 오른쪽에 있을 경우 x2를 선택하여 x를 직사각형 범위 안으로 끌어들이는 역할을 합니다.
• max(x1, ...)는 직사각형의 좌측 경계 x1과 이전 단계의 결과 중 더 큰 값을 선택합니다. 이는 x가 x1보다 왼쪽에 있을 경우 x1을 선택하여 x를 직사각형 범위 안으로 끌어들이는 역할을 합니다.
• 결과적으로, cx는 원의 중심 x가 직사각형의 x-범위 [x1, x2] 안에 있다면 x가 되고, x1보다 왼쪽에 있다면 x1이 되며, x2보다 오른쪽에 있다면 x2가 됩니다. 즉, x를 [x1, x2] 범위로 "클램핑(clamping)"하는 효과를 가집니다.

2단계: 직사각형 내 가장 가까운 y-좌표 찾기

• cy = max(y1, min(y, y2))
• 1단계와 동일한 논리로, 원의 중심 y 좌표를 기준으로 직사각형 내에서 가장 가까운 y-좌표 cy를 결정합니다.
• cy는 원의 중심 y가 직사각형의 y-범위 [y1, y2] 안에 있다면 y가 되고, y1보다 아래에 있다면 y1이 되며, y2보다 위에 있다면 y2가 됩니다. 즉, y를 [y1, y2] 범위로 "클램핑(clamping)"합니다.
• 이제 (cx, cy)는 원의 중심 (x, y)에서 직사각형의 경계 또는 내부에 있는 점 중 가장 가까운 점이 됩니다.

3단계: 원의 중심과 가장 가까운 직사각형 점 사이의 거리 계산 및 비교

• if (x-cx)**2 + (y-cy)**2 <= r ** 2:
• 이 단계에서는 원의 중심 (x, y)와 직사각형 내 가장 가까운 점 (cx, cy) 사이의 유클리드 거리의 제곱을 계산합니다.
  • 두 점 (x1, y1)과 (x2, y2) 사이의 거리 공식은 sqrt((x2-x1)^2 + (y2-y1)^2)입니다.
  • 거리의 제곱은 (x2-x1)^2 + (y2-y1)^2입니다.
• 제곱근(sqrt) 연산은 상대적으로 비용이 많이 들고 부동 소수점 오차를 발생시킬 수 있습니다. 따라서 실제 거리를 계산하는 대신, 거리의 제곱과 반지름의 제곱을 비교하는 방식을 사용합니다. A <= B 와 sqrt(A) <= sqrt(B)는 A, B >= 0일 때 동치이기 때문입니다.
• r ** 2는 원의 반지름의 제곱입니다.
• 만약 원의 중심 (x, y)에서 (cx, cy)까지의 거리의 제곱이 반지름의 제곱 r**2보다 작거나 같다면, 원과 직사각형은 겹칩니다. 이 경우 True를 반환합니다.

4단계: 결과 반환

• return True 또는 return False
• 조건문 if (x-cx)**2 + (y-cy)**2 <= r ** 2:이 참이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

⏱복잡도 분석

• 시간 복잡도: O(1)
  • 이 코드는 입력값의 크기(반지름, 좌표 값)에 관계없이 항상 고정된 수의 연산을 수행합니다. min, max 함수 호출, 덧셈, 뺄셈, 곱셈, 비교 연산 등이 모두 상수 시간에 이루어집니다. 따라서 시간 복잡도는 O(1)입니다.
• 공간 복잡도: O(1)
  • 이 코드는 입력으로 주어진 변수 외에 cx, cy 두 개의 변수만을 추가적으로 사용합니다. 이 변수들은 입력 크기에 따라 추가적인 공간을 필요로 하지 않으므로, 공간 복잡도는 O(1)입니다.

핵심 포인트

1. 원의 중심에서 직사각형까지의 최단 거리 활용: 원과 직사각형의 겹침 여부를 판단하는 가장 효율적인 방법은 원의 중심에서 직사각형 내부 또는 경계까지의 최단 거리를 계산하고, 이를 반지름과 비교하는 것입니다.
2. 클램핑(Clamping)을 이용한 최단 거리 점 찾기: max(lower_bound, min(value, upper_bound)) 패턴은 어떤 값을 특정 범위 [lower_bound, upper_bound] 내로 제한(클램핑)할 때 유용하게 사용됩니다. 이 문제에서는 원의 중심 좌표 (x, y)를 직사각형의 [x1, x2] 및 [y1, y2] 범위로 클램핑하여 직사각형 위에서 원의 중심에 가장 가까운 점 (cx, cy)을 찾는 데 활용되었습니다.
3. 제곱 거리 비교: 실제 거리 sqrt(d^2)를 계산하는 대신 거리의 제곱 d^2을 반지름의 제곱 r^2과 비교합니다. 이는 불필요한 제곱근 연산을 피하여 연산 비용을 줄이고, 부동 소수점 정밀도 문제(rounding error)를 방지하는 효과적인 방법입니다.

풀이 코드

class Solution:
    def checkOverlap(self, r: int, x: int, y: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        cx = max(x1, min(x, x2))
        cy = max(y1, min(y, y2))

        if (x-cx)**2 + (y-cy)**2 <= r ** 2:
            return True

        return False