24. 최대 공백 정사각형 [11 1주차]

24. 최대 공백 정사각형 [11-1주차]

2024년 1월 14일 일요일

오전 3:08

<최대 공백 정사각형>

주어진 nxn 픽셀의 흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 정사각형(최대 공백 정사각형)을 구하는 문제이다.

 

 

<최대 공백 정사각형 알고리즘 점화식>

각 픽셀마다 그 픽셀을 우측 하단 꼭짓점으로 하는 가장 큰 공백 정사각형의 변 길이를 적는다.

 

(x, y)픽셀에 적힌 숫자를 LES(x, y)라 한다.

 

(x, y)를 우측 하단 꼭짓점으로 하는 m x m크기의 정사각형을 S라 하자.

S가 비어 있을 필요충분조건은 다음과 같다.

1.     S의 가장 우측 하단 픽셀이 비어있다.

2.     S의 좌측상단, 좌측하단, 우측상단의 크기 (m-1) x (m-1) 정사각형이 비어있다.

 

이를 통해, 다음을 알 수 있다.

(x, y)픽셀은 비어 있고,

LES(x-1, y-1), LES(x-1, y), LES(x, y-1) 세 개의 값 중 가장 작은 것이 k-1이라 하자.

이때, 위에서 언급한 비어 있는 정사각형 S의 변 길이는 k가 될 수 있고, k+1이상은 될 수 없기 때문에, 다음 점화식이 성립한다.

 

LES(x, y)의 값은

1.     픽셀 (x, y)가 비어있지 않다면 LES(x, y) = 0

2.     첫번째 행 또는 열의 픽셀 (x, y)가 비어있다면 LES(x, y) = 1

3.     나머지 픽셀 (x, y)가 비어있다면

LES(x,y) = min { LES(x-1, y-1), LES(x, y-1), LES(x-1, y) } + 1

 

 

<최대 공백 정사각형 table과 코드>

 

 

 

 

<최대 공백 직사각형>

최대 공백 '직'사각형을 구하는 것은 좀 더 복잡하다.

 

전체 사각형에 수평선을 하나 긋는다. 일단 그 수평선의 일부분을 밑변으로 하는 직사각형만 생각할 것이다.

 

각 x좌표마다, 가로변의 길이가 1이고 밑변이 수평선 위에 있는 공백 직사각형의 최대 높이를 구한다. 그리고 각 직사각형을 파랗게 칠한다.

부분 문제는, 위의 파란 영역 내의 최대 공백 직사각형을 구하는 것이 된다.

 

 

<파란 영역 내의 최대 공백 직사각형 구하기>

x좌표가 i인 직사각형을 i번 직사각형이라 하고, i번 직사각형의 높이를 h(i), 높이가 h(i)이고 i번 직사각형을 포함하는 최대 공백 직사각형의 넓이를 R(i)라 한다.

 

i번 직사각형의 윗변을 연장했을 때, 왼쪽에서 막히기까지의 거리를 l(i), 오른쪽에서 막히기까지의 거리를 r(i)라 한다. 그러면

가 성립한다.

 

l(i)와 r(i)를 구하는 과정을 살펴보자. 스택 S에는 다음 조건을 만족하는 k번 직사각형들이 저장되어 있다.

1.     k<i

2.     k<k'<i인 k'에 대해, h(k)<=h(k')

위에서 V표시한 직사각형들이 S에 저장된다.

l(i)를 구하기 위해, S에 저장된 직사각형들의 높이만 고려하면 된다.

• h(k)>h(i)라면, r(k) = i-k-1 을 대입하고, S에서 k를 제거한다.
• h(k)<h(i)라면, l(i) = i-k-1 을 대입하고, S에 i를 추가한다.
• h(k)=h(i)라면, l(i) = i-k 을 대입하고, S에 i를 추가한다.

이러한 과정을 통해 모든 i에 대해 l(i)와 r(i)를 구할 수 있다.

 

 

<최대 공백 직사각형 구하기>

이 과정을 사각형의 밑변을 포함하게 되는 모든 n개의 수평선에 대해 수행한다.

하나의 수평선에 대해, h(i)를 모두 구하는 데 O(n²), R(i)를 모두 구하는 데 O(n²)이 걸린다. 수평선이 n개이므로, 총 O(n³)이 걸린다.

 

그러나 맨 위의 수평선에 대해 높이를 계산하고, 위에서 j번째 수평선은 j-1번째 수평선에 대해 계산한 높이들을 이용해 계산하면(동적계획법) 높이를 계산하는 데 수평선마다 O(n)의 시간만 걸린다.

 

따라서 전체 시간복잡도는 O(n²)이다.