여러분은 이제 알고리즘 문제 중 하나인 “선분의 교차 여부 구하기”에 대해서 자세히 살펴보려 합니다. 이번 강좌에서는 이 문제를 해결하기 위한 이론과 실제 구현 과정을 단계별로 설명하겠습니다. 알고리즘 문제 해결 능력을 향상시키고 싶은 분들에게 매우 유익할 것입니다.
문제 정의
선분의 교차 여부를 구하는 문제는 주어진 두 선분이 서로 교차하는지 여부를 판단하는 문제입니다. 이를 위해 두 선분 A(x1, y1)에서 B(x2, y2)로, C(x3, y3)에서 D(x4, y4)로 표현해보겠습니다. 문제는 다음과 같습니다:
두 선분 AB와 CD가 주어졌을 때, 두 선분이 교차하는지 여부를 판별하라.
입력 형식
입력은 4개의 정수로 이루어지며, 각 정수는 해당 선분의 끝점을 나타냅니다:
- A(x1, y1)
- B(x2, y2)
- C(x3, y3)
- D(x4, y4)
출력 형식
선분이 서로 교차하면 “YES”를, 그렇지 않으면 “NO”를 출력합니다.
문제 해결을 위한 기초 이론
선분이 교차하는 경우를 판단하기 위해 우리가 사용할 수 있는 방법 중 하나는 기하학적 방법입니다. 특히, 벡터의 크로스 제품을 활용하여 두 선분이 서로 교차하는지 여부를 판별할 수 있습니다.
크로스 제품
두 벡터 AB(x2-x1, y2-y1)와 AC(x3-x1, y3-y1) 사이의 크로스 제품은 다음과 같이 정의됩니다:
Cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
이 값을 통해 두 벡터의 방향을 알 수 있으며, 만약 크로스 제품의 값이 0이면 벡터가 일직선상에 있음을 의미하고, 양의 값이면 한 방향, 음의 값이면 반대 방향을 의미합니다.
선분의 교차 조건
두 선분 AB와 CD의 교차 여부를 판단하기 위해서 다음과 같은 조건을 확인해야 합니다:
- 두 선분이 “일반적인 경우”일 때: (AB와 CD의 각 끝점들이 서로 다른 방향에 있는 경우)
- 두 선분이 “단일 점에서 만날 때” (내부의 한 점에서 만날 경우)
- 두 선분이 “끝점에서 만날 때” (한 선분의 끝점이 다른 선분 위에 있을 경우)
일반적인 경우
선분 AB와 CD가 서로 다른 방향에 있는지를 확인하기 위해서는 A, B 두 점과 C를 이용한 크로스 제품과 A, B 두 점과 D를 이용한 크로스 제품의 부호를 비교합니다. 두 선분이 서로 다른 방향에 있는 경우 이 두 부호가 달라야 합니다.
단일/끝점에서 만나는 경우
일반적인 경우와는 다르게, 교차하는 것이 아니라 점에서 만나는 경우를 판단하려면 선분의 끝점이 서로의 선분 위에 있는지 확인해야 합니다.
파이썬 코드 구현
위의 기초 이론을 바탕으로, 우리는 다음과 같은 파이썬 코드를 작성할 수 있습니다.
def orientation(px, py, qx, qy, rx, ry):
val = (qy - py) * (rx - qx) - (qx - px) * (ry - qy)
if val == 0: return 0 # 콜리니어
return 1 if val > 0 else 2 # 시계 or 반시계
def on_segment(px, py, qx, qy, rx, ry):
return min(px, qx) <= rx <= max(px, qx) and min(py, qy) <= ry <= max(py, qy)
def do_intersect(p1, q1, p2, q2):
o1 = orientation(p1[0], p1[1], q1[0], q1[1], p2[0], p2[1])
o2 = orientation(p1[0], p1[1], q1[0], q1[1], q2[0], q2[1])
o3 = orientation(p2[0], p2[1], q2[0], q2[1], p1[0], p1[1])
o4 = orientation(p2[0], p2[1], q2[0], q2[1], q1[0], q1[1])
if o1 != o2 and o3 != o4:
return True
if o1 == 0 and on_segment(p1[0], p1[1], q1[0], q1[1], p2[0], p2[1]):
return True
if o2 == 0 and on_segment(p1[0], p1[1], q1[0], q1[1], q2[0], q2[1]):
return True
if o3 == 0 and on_segment(p2[0], p2[1], q2[0], q2[1], p1[0], p1[1]):
return True
if o4 == 0 and on_segment(p2[0], p2[1], q2[0], q2[1], q1[0], q1[1]):
return True
return False
# 테스트 케이스
A = (0, 0)
B = (10, 10)
C = (0, 10)
D = (10, 0)
if do_intersect(A, B, C, D):
print("YES")
else:
print("NO")
코드 설명과 테스트 케이스
위의 코드에서 먼저 orientation 함수는 세 점의 상대적인 위치를 파악합니다. on_segment 함수는 한 점이 정해진 선분 위에 있는지를 확인합니다. do_intersect 함수는 두 선분이 교차하는지를 판별합니다. 코드의 마지막 부분에서는 실제 테스트 케이스를 통해 결과를 확인할 수 있습니다.
결론
이번 강좌에서는 “선분의 교차 여부 구하기” 문제를 해결하기 위한 다양한 이론적 배경과 파이썬 코드 구현을 살펴보았습니다. 특정 알고리즘 문제를 풀어보며 기하학적 사고능력과 프로그래밍 능력을 함께 향상시킬 수 있는 기회가 되었기를 바랍니다. 앞으로도 여러분의 코딩 능력이 더욱 발전하길 기원합니다!