좌표 평면 위에 주어진 점들 중에서 변이 x축과 y축에 평행한 정사각형을 이루는 네 점을 찾는 문제는 기하 알고리즘의 대표적인 유형입니다. 이 글에서는 단순한 완전 탐색 방식부터 맵(map)을 활용한 효율적인 풀이까지, C++ 코드와 함께 자세히 살펴보겠습니다.
문제 개념
주어진 'n'개의 점 쌍 가운데 네 점을 골라, 변이 x축과 y축에 평행한 정사각형을 만들어야 합니다. 조건을 만족하는 정사각형이 존재하지 않으면 "No such square"를 출력합니다.
또한 하나의 규칙이 있습니다. 가능한 정사각형이 여러 개라면 반드시 면적이 가장 큰 정사각형을 선택해야 합니다.
입력 및 출력 예시
예시 1 — 정사각형이 존재하는 경우
입력:
n = 6, points = (2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)
출력:
Side of the square is : 3, points of the square are 2, 2 5, 2 2, 5 5, 5
설명: (2, 2), (5, 2), (2, 5), (5, 5) 네 점이 한 변의 길이가 3인 정사각형을 이룹니다.
예시 2 — 정사각형이 존재하지 않는 경우
입력:
n = 6, points = (2, 2), (5, 6), (4, 5), (5, 4), (8, 5), (4, 2)
출력:
No such square
풀이 방법
1. 단순한 방법 (완전 탐색)
네 개의 중첩 루프를 사용해 가능한 모든 점 조합을 선택한 뒤, 해당 네 점이 주축(x축, y축)에 평행한 정사각형을 이루는지 검증합니다. 정사각형이 맞다면 지금까지 발견한 정사각형보다 면적이 더 큰지 확인하고 결과를 저장하며, 프로그램이 끝날 때 최종 결과를 출력합니다.
- 시간 복잡도: O(N⁴)
N이 커지면 매우 비효율적이므로, 실전에서는 아래의 효율적인 방법을 사용하는 것이 좋습니다.
2. 효율적인 방법 (맵 활용)
정사각형의 대각선에 위치한 두 꼭짓점(오른쪽 위, 왼쪽 아래)에 대해 중첩 루프를 구성합니다. 두 점으로 정사각형을 가정한 후, 나머지 두 꼭짓점이 실제로 존재하는지만 확인하면 됩니다.
특정 점의 존재 여부를 빠르게 판단하기 위해 맵(map)에 모든 점을 미리 저장해 두면 조회 시간을 크게 줄일 수 있습니다. 탐색 과정에서도 지금까지 찾은 정사각형 중 면적이 가장 큰 것을 계속 추적하여, 마지막에 최댓값을 출력합니다.
- 시간 복잡도: O(N²)
- 공간 복잡도: O(N)
C++ 구현 예제
// 위 접근 방식의 C++ 구현
#include <bits/stdc++.h>
using namespace std;
// 가장 큰 정사각형을 찾는 함수
void findLargestSquare1(long long int points1[][2], int n1){
// 존재하는 점들을 저장하기 위한 맵
map<pair<long long int, long long int>, int> m1;
// 사용 가능한 점들을 맵에 표시
for (int i = 0; i < n1; i++) {
m1[make_pair(points1[i][0], points1[i][1])]++;
}
long long int side1 = -1, x1 = -1, y1 = -1;
// 정사각형의 대각선 양 끝 꼭짓점을 고르기 위한 중첩 루프
for (int i = 0; i < n1; i++) {
// 이미 선택한 점은 임시로 제거
m1[make_pair(points1[i][0], points1[i][1])]--;
for (int j = 0; j < n1; j++) {
// 이미 선택한 점은 임시로 제거
m1[make_pair(points1[j][0], points1[j][1])]--;
// 나머지 두 점이 존재하는지 확인
if (i != j && (points1[i][0]-points1[j][0]) == (points1[i][1]-points1[j][1])){
if (m1[make_pair(points1[i][0], points1[j][1])] > 0
&& m1[make_pair(points1[j][0], points1[i][1])] > 0) {
// 지금까지 찾은 것보다 큰 정사각형이면 저장
if (side1 < abs(points1[i][0] - points1[j][0])
|| (side1 == abs(points1[i][0] - points1[j][0])
&& ((points1[i][0] * points1[i][0] + points1[i][1] * points1[i][1])
< (x1 * x1 + y1 * y1)))) {
x1 = points1[i][0];
y1 = points1[i][1];
side1 = abs(points1[i][0] - points1[j][0]);
}
}
}
// 제거했던 점을 다시 추가
m1[make_pair(points1[j][0], points1[j][1])]++;
}
// 제거했던 점을 다시 추가
m1[make_pair(points1[i][0], points1[i][1])]++;
}
// 가장 큰 정사각형 출력
if (side1 != -1)
cout << "Side of the square is : " << side1
<< ", \npoints of the square are " << x1 << ", " << y1 << " "
<< (x1 + side1) << ", " << y1 << " "
<< (x1) << ", " << (y1 + side1) << " "
<< (x1 + side1) << ", " << (y1 + side1) << endl;
else
cout << "No such square" << endl;
}
// 드라이버 코드
int main(){
int n1 = 6;
// 주어진 점들
long long int points1[n1][2] = { { 2, 2 }, { 5, 5 }, { 4, 5 }, { 5, 4 }, { 2, 5 }, { 5, 2 } };
// 가장 큰 정사각형 찾기
findLargestSquare1(points1, n1);
return 0;
}실행 결과
Side of the square is : 3, points of the square are 2, 2 5, 2 2, 5 5, 5
핵심 포인트 정리
- 두 대각선 꼭짓점의 x좌표 차이와 y좌표 차이가 같아야(|x₁−x₂| = |y₁−y₂|) 축에 평행한 정사각형이 성립합니다.
- 맵을 사용하면 나머지 두 꼭짓점의 존재 여부를 O(log N)에 확인할 수 있어 전체 탐색이 O(N²)로 줄어듭니다.
- 같은 크기의 정사각형이 여러 개일 경우를 대비해 동점 처리 조건(원점에서의 거리 비교)도 함께 고려하는 것이 안전합니다.