[Python] 프로그래머스. 가장 큰 정사각형 (Level 2)

https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스

 

DP를 사용해 풀 수 있는 문제.

 

board의 y좌표, x좌표를 기준으로 볼 때

board[y-1][x-1], board[y][x-1], board[y-1][x] 세 개의 좌표값이 전부 1이라면

board[y][x]는 세 개의 정사각형이 왼쪽, 위쪽, 왼쪽 대각선에 포진해 있게 된다.

따라서 이 경우 결과적으로 정사각형 4개가 붙어 있는 모양이 되므로 변의 길이가 2인 정사각형이 된다.

 

따라서 DP 점화식을

board[y][x] = max(min(board[y-1][x-1], board[y-1][x], board[y][x-1]) +1, board[y][x])

로 세우면 된다.

 

대신 board[y][x] 값이 0인 경우, min() 값이 0인 경우에는 정사각형이 아니므로 점화식에 포함하지 않는다.

 

 

 

 

	from itertools import chain
	def solution(board):
	height = len(board)
	width = len(board[0])
	for i in range(1, height):
	for j in range(1, width):
	mins = min(board[i-1][j-1], board[i-1][j], board[i][j-1])
	if board[i][j] == 0 or mins == 0:
	continue
	board[i][j] = max(mins + 1, board[i][j])
	return max(list(chain.from_iterable(board))) ** 2

view raw [프로그래머스] 가장 큰 정사각형.py hosted with ❤ by GitHub