가장 큰 정사각형 찾기

문제 출처 및 풀이 코드

코딩테스트 연습

문제 요약

• 1과 0으로 채워진 이중 리스트에서 각 항목은 1x1 크기의 정사각형이다.
• 이 때 1로 이루어진 제일 큰 정사각형의 크기 구하기

제한 사항

• 행의 크기 : 1000 이하의 자연수
• 열의 크기 : 1000 이하의 자연수

문제 풀이

• 왼쪽은 주어진 보드 값을 나타내고, 오른쪽은 문제 해결 진행 과정 중에서 그려지는 표로 각 지점은 해당 지점이 정사각형의 우하단 지점일 때 최대로 그려지는 정사각형의 한 변의 길이를 나타낸다.
• 정사각형의 크기를 체크하는 코드의 진행이 이중 리스트의 for문을 따라서 우측으로, 그리고 하단으로 이동하게 된다. 그래서 오른쪽의 테이블도 오른쪽으로 그리고 아래로 채워지게된다.
• 이동하는 체크하는 위치는 정사각형의 우하단의 정점이라고 하자.
• 위의 그림에서 빨간색 원 기준으로 가장 넓은 정사각형이 무엇인지를 판단하기 위해서는(파란색 물음표) 왼쪽에서 1이라면, 오른쪽 표에서 녹색원에 해당하는 지점이 (해당 지점의 상단, 좌측, 그리고 좌상단 지점)들의 값중 가장 작은 값에 1을 더한 값이 된다.
  • 왜냐하면 저 녹색 지점이 모두 같은 크기의 정사각형일 때 파란색 지점의 1을 더하여 그것보다 변의 길이가 1이 큰 정사각형이 완성되기 때문이다.

코드

def solution(board):
    
	# board의 높이
    h = len(board)
		
	# board의 너비
    w = len(board[0])
    
	# 사각형의 최대 크기의 기본값. 
	# 만약에 표 내에 1이 없으면 0 값을 가진다.
    max_square = 1 if max(max(board)) == 1 else 0
    
	# 첫 행으로 만들 수 있는 정사각형의 크기는 1이므로 제외한다. 
    for i in range(1, h):
		# 첫 열로 만들 수 있는 정사각형의 크기는 1이므로 제외한다.
        for j in range(1, w):
				# 만약 우하단으로 잡은 지점이 값이 1이라면
		        if board[i][j] == 1:
                
				# 해당 위치의 좌측, 상단, 그리고 좌상단 값중 가장 작은 값에 1을 더한 크기가 
				# 해당 위치를 우하단이라하였을 때 만들 수 있는 가장 큰 정사각형의 한 변의 길이
                board[i][j] = min(board[i-1][j-1], board[i][j-1], board[i-1][j]) + 1
                
				# 정사각형의 크기는 변의 제곱이므로 제곱하여 기존의 크기과 값을 비교한다.
                max_square = max(max_square, (board[i][j])**2)
                              
    return max_square