문제 설명
반지름이 각각 r1과 r2인 두 개의 구가 있다고 가정해 봅시다. 첫 번째 구의 위치는 (x1, y1, z1), 두 번째 구의 위치는 (x2, y2, z2)이며, 각 구의 가속도는 (ax1, ay1, az1)과 (ax2, ay2, az2)로 주어집니다. 우리가 해야 할 일은 이 두 구가 주어진 가속도로 움직일 때 3차원 공간에서 언젠가 서로 만나는 순간이 있는지, 즉 충돌하는지를 판별하는 것입니다.
예를 들어 입력이 r1 = 1, r2 = 2, pos1 = (0, 0, 0), acc1 = (100, 0, 0), pos2 = (4, 0, 0), acc2 = (0, 0, 0)라고 해 보겠습니다. 이 경우 출력은 True입니다. 두 번째 구에는 가속도가 없으므로 제자리에 머무르지만, 첫 번째 구는 x축 방향으로 빠르게 이동하여 결국 두 번째 구와 충돌하게 되기 때문입니다.
접근 방법
이 문제의 핵심은 상대 운동(relative motion)의 관점에서 바라보는 것입니다. 한 구를 기준점으로 삼으면, 다른 구는 두 구 사이의 상대 위치와 상대 가속도에 따라 움직이는 하나의 점처럼 취급할 수 있습니다. 등가속도 운동에서 두 점 사이의 거리는 시간 t에 대한 2차 함수(포물선) 형태가 되므로, 거리가 최소가 되는 시점을 구하고 그때의 거리가 두 구의 반지름 합(r1 + r2)보다 작거나 같으면 두 구는 반드시 만나거나 충돌하게 됩니다.
구체적인 풀이 과정은 다음과 같습니다.
- px := pos1[0] − pos2[0]
- py := pos1[1] − pos2[1]
- pz := pos1[2] − pos2[2]
- ax := acc1[0] − acc2[0]
- ay := acc1[1] − acc2[1]
- az := acc1[2] − acc2[2]
- da := ax·ax + ay·ay + az·az (상대 가속도 벡터 크기의 제곱)
- dp := px·px + py·py + pz·pz (초기 상대 위치 벡터 크기의 제곱)
- co := ax·px + ay·py + az·pz (두 벡터의 내적)
- x := 0.0
- 만약 da가 0이 아니라면
x := −co / da (거리가 최소가 되는 시점) - x := max(x, 0) (시간은 음수가 될 수 없으므로 0 이하로 클램프)
- dis := √(da·x² + 2·co·x + dp) (최소 거리 계산)
- 만약 dis ≤ r1 + r2이면 True 반환, 그렇지 않으면 False 반환
예제 코드
아래 구현을 통해 더 자세히 이해해 봅시다.
def solve(r1, r2, pos1, acc1, pos2, acc2):
px, py, pz = pos1[0] - pos2[0], pos1[1] - pos2[1], pos1[2] - pos2[2]
ax, ay, az = acc1[0] - acc2[0], acc1[1] - acc2[1], acc1[2] - acc2[2]
da = (ax * ax + ay * ay + az * az)
dp = (px * px + py * py + pz * pz)
co = (ax * px + ay * py + az * pz)
x = 0.0
if da != 0:
x = - co / da
x = max(x, 0)
dis = (da * x * x + 2 * co * x + dp) ** 0.5
if dis <= r1 + r2:
return True
else:
return False
r1 = 1
r2 = 2
pos1 = (0, 0, 0)
acc1 = (100,0,0)
pos2 = (4, 0, 0)
acc2 = (0,0,0)
print(solve(r1, r2, pos1, acc1, pos2, acc2))입력
1, 2, (0, 0, 0), (100,0,0), (4, 0, 0), (0,0,0)
출력
True
복잡도 분석
모든 연산이 고정된 횟수의 산술 연산으로만 이루어지므로, 이 알고리즘의 시간 복잡도는 O(1)이며 공간 복잡도 역시 O(1)입니다. 따라서 입력 크기와 무관하게 매우 빠르게 결과를 얻을 수 있습니다.