[BOJ/백준] 1915 가장 큰 정사각형

# 실패한 방법

N,M = map(int,input().split())

arr = [list(map(int,list(input()))) for _ in range(N)]
result = 0
max_size = min(N,M)

for x in range(N):
    for y in range(M):
        if result == max_size:
            break
        if arr[x][y] == 1:
            for sizes in range(result,max_size+1):
                temp = 0
                for dx in range(sizes):
                    for dy in range(sizes):
                        if 0<=x+dx<N and 0<=y+dy<M: 
                            temp += arr[x+dx][y+dy]
                if temp == sizes**2:
                    result = sizes
                else:
                    break
print(result**2)

처음에 단순하게 현재의 max_size만큼을 각 위치에서 탐색을 해서 갱신해주는 방식을 했다. 이렇게 하니 시간 초과가 나왔다.

 

N,M = map(int,input().split())
arr = [[0]*(M+1)]
for _ in range(N):
    arr.append([0]+list(map(int,list(input()))))
result = 0
max_size = min(N,M)

for x in range(1,N+1):
    for y in range(1,M+1):
        if arr[x][y]:
            arr[x][y] = min(arr[x-1][y],arr[x][y-1],arr[x-1][y-1])+1
            result = max(arr[x][y],result)
        if result == max_size:
            break

print(result**2)

1	1
1	1

위와 같은 정사각형이 있으면,  우하단을 기준으로 상하, 대각선이 전부 1이어야만 정사각형이 모양이된다. 만약 3개 중 하나라도 0이 있으면 크기가 2인 정사각형이 모양이 안된다. 그러므로 여기서 될수 있는 정사각형의 크기는 2이다.

 

1	1
1	2

이걸 좀 더 확장해서 3*3를 그려보도록 하자.

1	1	1
1	1	1
1	1	1

위와 같이 있다고 했을때 행과 열 중 0인 곳은 크기가 1를 초과하는 것을 못 만드므로 예외로 하겠다. 그러면 실질적으로 1,1 부터 탐색을 한다.

1	1	1
1	2	2
1	2	3

위와 같은 로직으로 하면 다음과 같이 우하단이 3이 되는 것을 알 수 있다 

1	1	1
0	1	1
1	1	1

이렇게 한군데가 비어있으면

 

1	1	1
0	1	2
1	1	2

이렇듯 우하단이 2가 되는 것을 알 수 있다.

 

그러므로 이 문제는 (x,y) 좌표 기준으로 (x-1,y),(x,y-1),(x-1,y-1)의 값의 최소값에 + 1을 해주면 된다.

 

그리고 저장된 값 중에서 가장 큰 값이 이 행렬에서 제일 큰 정사각형이므로, 제곱을 해서 출력을 하면 된다.