문제 설명
0은 흰색 픽셀, 1은 검은색 픽셀을 나타내는 이진 행렬(binary matrix)로 이미지가 표현되어 있다고 가정해 보겠습니다. 검은색 픽셀들은 서로 연결되어 있어 검은색 영역은 단 하나만 존재하며, 픽셀은 가로와 세로 방향으로 연결됩니다. 이때 검은색 픽셀 중 하나의 위치 (x, y)가 주어지면, 모든 검은색 픽셀을 감싸는 가장 작은 축 평행(axis-aligned) 사각형의 넓이를 구해야 합니다.
예를 들어 입력 이미지가 다음과 같다고 합시다.
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 |
x = 0, y = 2가 주어지면 출력 결과는 6이 됩니다.
해결 접근 방법
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 주어진 검은 픽셀의 위치 (x, y)를 기준으로 위(top), 아래(bottom), 왼쪽(left), 오른쪽(right) 네 방향의 경계를 각각 이진 탐색으로 찾아낸 뒤, 너비와 높이를 곱하여 넓이를 계산합니다.
전체 알고리즘은 다음과 같습니다.
- 2차원 배열 v를 정의하고 이미지 데이터를 저장합니다.
- searchRows() 함수를 정의합니다. 이 함수는 i, j, left, right, one을 매개변수로 받으며, 행 방향으로 이진 탐색을 수행합니다.
- i < j인 동안 반복합니다.
- mid := i + (j - i) / 2 로 중간 위치를 계산합니다.
- k := left 에서 시작해, k < right이고 v[mid][k]가 '0'인 동안 k를 1씩 증가시킵니다.
- (k < right)의 결과가 one과 같으면 j := mid로 범위를 좁히고, 그렇지 않으면 i := mid + 1로 진행합니다.
- 반복이 끝나면 i를 반환합니다.
- searchColumn() 함수도 같은 원리로 정의합니다. i, j, top, bottom, one을 받으며, 열 방향으로 이진 탐색을 수행해 검은 픽셀이 존재하는 경계 열을 찾습니다.
- 메인 로직에서 네 방향의 경계를 다음과 같이 구합니다.
- top := searchRows(0, x, 0, m, true)
- bottom := searchRows(x + 1, n, 0, m, false)
- left := searchColumn(0, y, top, bottom, true)
- right := searchColumn(y + 1, m, top, bottom, false)
- 최종적으로 (right - left) × (bottom - top)을 반환합니다.
여기서 one 매개변수는 탐색 방향을 결정합니다. true이면 주어진 위치에서 위쪽(또는 왼쪽)으로 검은 픽셀이 처음 나타나는 경계를, false이면 아래쪽(또는 오른쪽) 경계를 찾습니다. 각 이진 탐색 단계에서 한 행 또는 한 열을 스캔하므로, 전체 시간 복잡도는 O(m log n + n log m) 수준으로, 모든 픽셀을 순회하는 O(n×m) 완전 탐색보다 효율적입니다.
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector < vector <char> > v;
int searchRows(int i, int j, int left, int right, bool one){
while (i < j) {
int mid = i + (j - i) / 2;
int k = left;
while (k < right && v[mid][k] == '0')
k++;
if (k < right == one) {
j = mid;
}
else {
i = mid + 1;
}
}
return i;
}
int searchColumn(int i, int j, int top, int bottom, bool one){
while (i != j) {
int mid = i + (j - i) / 2;
int k = top;
while (k < bottom && v[k][mid] == '0')
k++;
if (k < bottom == one) {
j = mid;
}
else {
i = mid + 1;
}
}
return i;
}
int minArea(vector<vector<char>>& image, int x, int y) {
v = image;
int ret = 0;
int n = image.size();
int m = image[0].size();
int top = searchRows(0, x, 0, m, true);
int bottom = searchRows(x + 1, n, 0, m, false);
int left = searchColumn(0, y, top, bottom, true);
int right = searchColumn(y + 1, m, top, bottom, false);
return (right - left) * (bottom - top);
}
};
main(){
Solution ob;
vector<vector<char>> v =
{{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}};
cout << (ob.minArea(v, 0, 2));
}
입력
{{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}}, 0, 2
출력
6