C++로 주어진 좌표 집합에서 만들 수 있는 직사각형의 최소 넓이 구하기

XY 평면 위에 여러 점들이 배열 형태로 주어져 있다고 가정해 봅시다. 이 점들로 만들 수 있는 직사각형 중 가장 작은 넓이를 구하는 것이 목표입니다. 단, 직사각형의 변은 반드시 X축과 Y축에 각각 평행해야 하며, 직사각형을 만들 수 없는 경우에는 0을 반환해야 합니다.

예를 들어 점들의 배열이 [(1, 1), (1, 3), (3, 1), (3, 3), (2, 2)]와 같다면 결과는 4가 됩니다. 점 (1, 1), (1, 3), (3, 1), (3, 3) 네 개를 꼭짓점으로 하는 직사각형이 만들어지기 때문입니다. 가로 길이가 2, 세로 길이가 2이므로 넓이는 4입니다.

문제 해결 접근 방법

이 문제를 효율적으로 풀려면 먼저 모든 점을 x좌표 기준으로 정렬하여, 같은 세로선 위에 놓인 점들을 하나의 그룹으로 묶습니다. 그런 다음 각 그룹 안에서 (x, y1)과 (x, y2)처럼 두 점씩 짝지어 보면서, 이 두 점을 만들려는 직사각형의 오른쪽 변으로 삼았을 때 성립하는 가장 작은 직사각형을 찾습니다.

핵심 아이디어는 지금까지 살펴본 점 쌍들을 계속 기록해 두는 것입니다. 동일한 y좌표 쌍 (y1, y2)이 이전에 다른 x좌표에서 이미 등장했다면, 두 x좌표의 차이(가로 길이)와 y좌표 쌍의 차이(세로 길이)를 곱해 직사각형의 넓이를 계산할 수 있습니다. 이렇게 구한 넓이들 중 최솟값을 계속 갱신하고, 마지막에 그 값을 반환합니다. 만약 어떤 직사각형도 만들 수 없었다면 0을 반환합니다.

예제 코드

import collections
def findMinArea(Arr):
    columns = collections.defaultdict(list)
    for x, y in Arr:
        columns[x].append(y)
    lastx = {}
    ans = float('inf')
    for x in sorted(columns):
        col = columns[x]
        col.sort()
        for j, y2 in enumerate(col):
            for i in range(j):
                y1 = col[i]
                if (y1, y2) in lastx:
                    ans = min(ans, (x - lastx[y1, y2]) * (y2 - y1))
                lastx[y1, y2] = x
    if ans < float('inf'):
        return ans
    else:
        return 0

A = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
print('Minimum area of rectangle:', findMinArea(A))

출력 결과

Minimum area of rectangle: 4

코드 설명

columns 딕셔너리는 같은 x좌표를 가진 점들의 y값들을 모아 저장합니다. 이후 x좌표를 오름차순으로 순회하면서 각 열(column) 안의 y값들을 정렬한 뒤, 가능한 모든 (y1, y2) 쌍을 검사합니다. lastx 딕셔너리에는 각 y좌표 쌍이 마지막으로 등장한 x좌표가 저장되므로, 같은 쌍이 다시 나타나면 두 x좌표 사이의 거리를 바로 계산해 넓이를 구할 수 있습니다.

이 알고리즘의 시간 복잡도는 각 열에 속한 점들의 개수를 k라고 할 때, 열마다 발생하는 점 쌍의 조합 수에 비례하므로 대략 O(N²) 수준입니다. 점의 개수가 많아지더라도 불필요한 모든 점 조합을 검사하지 않고 같은 세로선 위의 점들만 비교하기 때문에 상당히 효율적으로 동작합니다.