N개의 축에 평행한(axis-aligned) 직사각형이 주어졌을 때, 이 직사각형들이 모두 합쳐져 하나의 직사각형 영역을 정확히 덮는지(exact cover) 판별해야 합니다. 여기서 '정확히 덮는다'는 것은 직사각형들 사이에 빈 공간도 없고, 서로 겹치는 부분도 없어야 한다는 의미입니다. 각 직사각형은 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점 두 좌표로 표현되며, 예를 들어 단위 정사각형은 [1,1,2,2]로 나타냅니다. 즉, 왼쪽 아래 점은 (1, 1), 오른쪽 위 점은 (2, 2)입니다.
예를 들어 입력이 rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]라고 한다면, 5개의 직사각형이 모두 하나의 직사각형 영역을 정확히 덮으므로 결과는 true가 됩니다.
문제 해결 접근 방법
이 문제의 핵심 아이디어는 두 가지 조건을 동시에 확인하는 것입니다.
- 면적 조건: 모든 작은 직사각형의 면적 합이 전체를 감싸는 경계 직사각형(bounding box)의 면적과 같아야 합니다.
- 꼭짓점 조건: 내부에서 만나는 꼭짓점들은 짝수 번 등장하여 서로 상쇄되어야 하며, 최종적으로 남는 꼭짓점은 경계 직사각형의 네 꼭짓점뿐이어야 합니다.
구체적인 알고리즘은 다음과 같습니다.
- 꼭짓점의 등장 여부를 추적하기 위한 집합(set) visited를 정의합니다.
- 누적 면적을 저장할 변수 area := 0으로 초기화합니다.
- x2 := -∞, x1 := +∞, y2 := -∞, y1 := +∞로 초기화합니다.
- 주어진 목록 re의 각 직사각형 r에 대해 다음을 수행합니다.
- x1 := min(r[0], x1)
- x2 := max(r[2], x2)
- y1 := min(r[1], y1)
- y2 := max(r[3], y2)
- area := area + ((r[2] - r[0]) × (r[3] - r[1]))
- 현재 직사각형의 네 꼭짓점을 문자열로 만듭니다. s1 := r[0]+r[1], s2 := r[0]+r[3], s3 := r[2]+r[3], s4 := r[2]+r[1]
- 각 꼭짓점 s1, s2, s3, s4에 대해 해당 꼭짓점이 이미 visited에 존재하면 삭제하고, 존재하지 않으면 삽입합니다. (토글 방식)
- 모든 순회가 끝나면 경계 직사각형의 네 꼭짓점을 만듭니다. s1 := x1+y1, s2 := x2+y1, s3 := x1+y2, s4 := x2+y2
- 이 네 꼭짓점이 모두 visited에 존재하지 않거나, visited에 남아 있는 원소의 개수가 정확히 4가 아니면 false를 반환합니다.
- 마지막으로 area가 ((x2 - x1) × (y2 - y1))과 같으면 true, 그렇지 않으면 false를 반환합니다.
예제 구현 (C++)
아래 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isRectangleCover(vector<vector<int>> &re) {
unordered_set<string> visited;
int area = 0;
int x2 = INT_MIN;
int x1 = INT_MAX;
int y2 = INT_MIN;
int y1 = INT_MAX;
for (auto &r : re) {
x1 = min(r[0], x1);
x2 = max(r[2], x2);
y1 = min(r[1], y1);
y2 = max(r[3], y2);
area += (r[2] - r[0]) * (r[3] - r[1]);
string s1 = to_string(r[0]) + to_string(r[1]);
string s2 = to_string(r[0]) + to_string(r[3]);
string s3 = to_string(r[2]) + to_string(r[3]);
string s4 = to_string(r[2]) + to_string(r[1]);
if (visited.count(s1)) {
visited.erase(s1);
}
else {
visited.insert(s1);
}
if (visited.count(s2)) {
visited.erase(s2);
}
else {
visited.insert(s2);
}
if (visited.count(s3)) {
visited.erase(s3);
}
else {
visited.insert(s3);
}
if (visited.count(s4)) {
visited.erase(s4);
}
else {
visited.insert(s4);
}
}
string s1 = to_string(x1) + to_string(y1);
string s2 = to_string(x2) + to_string(y1);
string s3 = to_string(x1) + to_string(y2);
string s4 = to_string(x2) + to_string(y2);
if (!visited.count(s1) || !visited.count(s2) || !visited.count(s3) || !visited.count(s4) || visited.size() != 4)
return false;
return area == (x2 - x1) * (y2 - y1);
}
};
main() {
Solution ob;
vector<vector<int>> v = {{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}};
cout << (ob.isRectangleCover(v));
}
입력
{{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}}
출력
1
동작 원리 요약
이 알고리즘은 시간 복잡도 O(N), 공간 복잡도 O(N)으로 동작합니다. 직사각형들 사이에 겹침이나 빈틈이 존재하면 면적 조건과 꼭짓점 조건 중 하나가 반드시 깨지게 됩니다. 따라서 두 조건을 모두 통과했다면, 주어진 직사각형들이 하나의 완벽한 직사각형을 이룬다고 확신할 수 있습니다.