문제 개요
2차원 평면 위에서 단순 다각형(simple polygon)의 꼭짓점들을 순서대로 나열한 좌표 목록이 주어졌다고 가정해 봅시다. 우리의 목표는 이 다각형의 넓이를 계산하는 것입니다.
예를 들어, 입력이 points = [(0, 0), (0, 5), (3, 5), (3, 0)]과 같다면, 해당 다각형은 가로 3, 세로 5인 직사각형이므로 결과는 15가 됩니다.
해결 접근 방법: 신발끈 공식(Shoelace Formula)
이 문제는 신발끈 공식(Shoelace Formula), 즉 사선 공식을 활용하면 효율적으로 해결할 수 있습니다. 인접한 두 꼭짓점의 좌표로 외적(cross product) 값을 누적한 뒤, 최종적으로 절댓값을 취하고 2로 나누면 다각형의 넓이를 얻을 수 있습니다.
구체적인 풀이 단계는 다음과 같습니다.
getInfo()함수를 정의합니다. 이 함수는 x1, y1, x2, y2 네 개의 값을 인자로 받습니다.x1*y2 - y1*x2를 반환합니다.- 메인 함수(
solve())에서는 아래 과정을 수행합니다. - N := points 리스트의 크기
- (firstx, firsty) := points[0] (첫 번째 꼭짓점 저장)
- (prevx, prevy) := (firstx, firsty)
- res := 0 (누적합 초기화)
- i를 1부터 N-1까지 반복하며:
- (nextx, nexty) := points[i]
- res := res + getInfo(prevx, prevy, nextx, nexty)
- prevx := nextx, prevy := nexty 로 갱신
- 마지막 꼭짓점과 첫 번째 꼭짓점을 연결: res := res + getInfo(prevx, prevy, firstx, firsty)
- |res| / 2.0 을 반환합니다.
예제 코드
아래 파이썬 구현 예제를 통해 동작 방식을 더 자세히 이해해 보겠습니다.
def getInfo(x1, y1, x2, y2):
return x1*y2 - y1*x2
def solve(points):
N = len(points)
firstx, firsty = points[0]
prevx, prevy = firstx, firsty
res = 0
for i in range(1, N):
nextx, nexty = points[i]
res = res + getInfo(prevx, prevy, nextx, nexty)
prevx = nextx
prevy = nexty
res = res + getInfo(prevx, prevy, firstx, firsty)
return abs(res)/2.0
points = [(0, 0), (0, 5), (3, 5), (3, 0)]
print(solve(points))
입력
[(0, 0), (0, 5), (3, 5), (3, 0)]
출력
15.0
동작 원리 및 복잡도 정리
이 알고리즘의 시간 복잡도는 O(N)으로, 꼭짓점 개수에 비례해 선형적으로 증가합니다. 각 변마다 외적을 한 번씩 계산해 누적하는 방식이기 때문에 볼록 다각형뿐 아니라 오목 다각형의 넓이도 정확하게 구할 수 있습니다. 다만, 변들이 서로 교차하지 않는 단순 다각형인 경우에만 올바른 결과가 보장된다는 점에 유의해야 합니다.