[Python] 1915 - 가장 큰 정사각형 (골드4)

1. 문제 설명

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

---

2. 아이디어

이 문제를 풀이하는 방법은 매우 다양하다. 브루트 포스, 분할 탐색, DP 등등..

N, M 크기가 작기 때문에 뭘 사용해도 상관 없지만 나는 그 중에서도 시간복잡도 O(N)인

스택을 이용한 알고리즘을 사용했다.

Make언어를 이용해서 C를 통해 구현해보면 1만X1만도 1초내로 끝난다. 뿌듯-!

 

우선 입력받은 맵을 히스토그램화 시킨다. 위에서 아래로 내려가면서 1씩 증가시키는데

만약 0이 나오면 초기화하고 그 아래부터는 다시 1에서 시작한다.

여기서 숫자는 각 좌표에서 위로 그릴 수 있는 최대 직사각형의 높이다.

그리고 반복문을 통해 각 row를 하나씩 살펴본다.

1열은 건너뛰고 2열부터 한 번 확인해보자.

 

 

처음 스택에는 무조건 높이 0을 의미하는 값을 넣어주고 시작해야 한다.

(-1, 0)은 각각 (width, heigth)를 의미한다고 보면 된다.

이후 히스토그램에 저장된 값을 스택의 가장 나중에 들어온 값과 비교하여

같거나 낮은 높이의 직사각형이 들어오면 스택에서 pop하고 새로운 값을 저장하고,

더 큰 값이 들어오면 그냥 쌓으면 된다.

이유는 조금 나중에 설명하고 일단 흐름대로라면 아래처럼 된다.

 

(-1, 0)과 (0, 0)은 같은 높이이므로 기존의 (-1, 0)을 pop한 후에 스택에는 (0, 0)을 담고

(1, 2)는 높이가 더 크므로 그냥 그대로 쌓아주면 된다.

문제는 바로 다음에 1의 높이인 사각형이 오는데 이때는 (1, 2)를 pop 해주어야 한다.

대체 이게 무슨 논리인 걸까??

생각해보면 (1, 2)라는 정보는 더이상 필요가 없다.

이미 현재 사각형보다 높이가 더 작은 사각형이 들어왔다는 것은 저 부분에서는 더이상

높이가 1보다 큰 정사각형이 들어올 수는 없다.

즉, 새로 들어온 더 낮은 높이의 사각형에 의해 만들어질 수 있는 정사각형의 높이가 제한되어 버린 것이다.

그렇다면 아직 스택에 남아있는 이전의 값의 x축 위치 정보를 통해 가로와 세로축의 값을 비교를 하고

더 작은 값이 현재까지 만들어질 수 있는 최대 정사각형의 한 변의 길이로 결정된다.

이 과정을 히스토그램 모든 열에 반복 수행하면 답을 얻을 수 있는 문제였다.

 

---

3. 코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(map(int, input().rstrip())) for _ in range(n)]
histogram = [[0]*(m+2) for _ in range(n)]
max_length = 0

def make_histogram():
    for col in range(1, m+1):
        cnt = 0
        for row in range(n):
            if board[row][col-1] == 1:
                cnt += 1
            else:
                cnt = 0
            histogram[row][col] = cnt

def search_square():
    global max_length
    
    stack = []

    for row in range(n):
        stack.append([-1, 0])
        col = 1
        while col < m+2:
            if stack[-1][1] < histogram[row][col]:
                stack.append([col-1, histogram[row][col]])
            elif stack[-1][1] > histogram[row][col]:
                y = stack[-1][1]
                stack.pop()
                x = stack[-1][0]
                
                if col - x - 2 > y:
                    length = y
                else:
                    length = col - x - 2

                if max_length < length:
                    max_length = length
                continue
            else:
                stack.pop()
                stack.append([col-1, histogram[row][col]])

            col += 1
        stack.clear()

def solution():
    global max_length

    make_histogram()
    search_square()

    print(pow(max_length, 2))
    return

solution()