Python으로 직사각형 영역에서 폭탄을 피해 연속 경로를 찾는 프로그램

문제 소개

각 원소가 [p, q, r] 형태로 이루어진 배열 mat이 주어졌다고 가정해 보겠습니다. 여기서 p와 q는 기하학적 좌표를 나타내고, r은 반경 값입니다. 배열의 각 항목은 폭이 w로 주어진 직사각형 영역 안에 놓여 있는 폭탄의 위치를 의미합니다. 이 직사각형은 무한히 길며, x 좌표 기준으로 x = 0부터 x = w 사이로 경계가 정해져 있습니다.

폭탄 위치에 포함된 r 값은 해당 폭탄의 안전 반경(safety radius)을 뜻합니다. 즉, 폭탄 중심에서 이 반경 이내로 접근하면 폭탄이 작동하게 됩니다. 따라서 우리가 해야 할 일은 모든 폭탄의 아래쪽에서 시작해 모든 폭탄의 위쪽에서 끝나는 연속적인 경로를 그리되, 어느 폭탄도 건드리지 않도록 하는 것입니다. 이런 경로를 그릴 수 있다면 True를, 불가능하다면 False를 출력합니다.

핵심 아이디어는 간단합니다. 만약 폭탄들의 안전 반경(원)들이 서로 겹쳐 왼쪽 경계(x = 0)부터 오른쪽 경계(x = w)까지 하나의 장벽처럼 이어진다면, 아래에서 위로 향하는 길은 완전히 막히게 됩니다. 이 경우 정답은 False입니다.

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

w = 4일 때 출력 결과는 False가 됩니다.

해결 절차

이 문제는 다음 단계에 따라 해결할 수 있습니다.

• 두 폭탄의 원이 서로 겹치는지 확인하는 함수 insec()을 정의합니다. 이 함수는 p, q 두 폭탄을 인자로 받습니다.
  • x1 := p[1], y1 := p[2]
  • x2 := q[1], y2 := q[2]
  • r1 := p[3], r2 := q[3]
  • d := (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
  • dec := (r1 + r2) * (r1 + r2)
  • d <= dec이면 True를, 그렇지 않으면 False를 반환합니다.
• 행렬을 x 좌표 값을 기준으로 정렬합니다.
• temp := 새로운 빈 리스트
• 만약 mat[0][0] - mat[0][2] > 0이라면(가장 왼쪽 폭탄이 왼쪽 경계에 닿지 않는 경우):
  • True를 반환합니다.
• mat의 각 (p, q, r)에 대해 다음을 수행합니다.
  • min_wid := p - r
  • max_wid := p + r
  • temp의 크기가 0이라면:
    • (p + r, p, q, r, p - r, p + r)을 담은 리스트를 temp의 끝에 추가합니다.
  • 그렇지 않으면:
    • mx := max(([p - r, -p, q, r, 0, 0]이 정렬 순서를 유지한 채 삽입될 수 있는 temp 내 위치 - 1), 0)
    • in_list := (p + r, p, q, r, p - r, p + r)을 담은 새 리스트
    • i를 mx부터 temp의 크기까지 반복하면서:
      • insec(temp[i], in_list)가 True라면:
        • max_wid = max(max_wid, temp[i][-1])
      • min_wid = min(min_wid, temp[i][-2])
  • in_list의 마지막에서 두 번째 원소 := min_wid
  • in_list의 마지막 원소 := max_wid
  • 정렬 순서를 유지하면서 in_list를 temp에 삽입합니다.
• 만약 min_wid <= 0이고 max_wid >= w라면:
  • False를 반환합니다.

예제

아래 구현을 통해 더 자세히 이해해 보겠습니다.

from bisect import bisect_left, insort
def solve(mat, w):
   mat.sort(key=lambda i: i[0] - i[2])
   temp = []
   if mat[0][0] - mat[0][2] > 0:
      return True
   for p, q, r in mat:
      min_wid, max_wid = p - r, p + r
      if len(temp) == 0:
         temp.append([p + r, p, q, r, p - r, p + r])
      else:
         mx = max(bisect_left(temp, [p - r, -p, q, r, 0, 0]) - 1, 0)

         in_list = [p + r, p, q, r, p - r, p + r]
         for i in range(mx, len(temp)):
             if insec(temp[i], in_list):
                max_wid = max(max_wid, temp[i][-1])
                min_wid = min(min_wid, temp[i][-2])
         in_list[-2] = min_wid
         in_list[-1] = max_wid
         insort(temp, in_list)
      if min_wid <= 0 and max_wid >= w:
         return False
   return True

def insec(p, q):
   x1, y1, x2, y2 = p[1], p[2], q[1], q[2]
   r1, r2 = p[3], q[3]
   d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
   dec = (r1 + r2) * (r1 + r2)
   return d <= dec

print(solve([[0, 1, 2],[3, 2, 1], [2, 1, 1]], 4))

코드 설명

이 알고리즘은 폭탄들을 왼쪽 끝점(p - r)을 기준으로 정렬한 뒤, 서로 겹치는 원들을 하나의 그룹으로 묶고 해당 그룹이 덮는 수평 구간 [min_wid, max_wid]를 추적합니다. bisect_left와 insort를 활용해 temp 리스트를 항상 정렬된 상태로 유지함으로써 비교 대상의 범위를 줄여 효율성을 높였습니다. 어떤 그룹의 구간이 왼쪽 경계(min_wid <= 0)와 오른쪽 경계(max_wid >= w)를 동시에 덮게 되면, 폭탄들이 좌우를 완전히 막아버린 것이므로 False를 반환하고, 그렇지 않으면 True를 반환합니다.

입력

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

출력

False