[파이썬🐍] 프로그래머스 : 가장 큰 정사각형 찾기

 

def solution(board):
    answer = 0
    for i in range(len(board)):
        for j in range(len(board[0])):
            if (i > 0) and (j > 0) and (board[i][j] != 0):
                board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1])+1
            answer = max(answer, board[i][j])
    return answer ** 2

처음엔 이 방법을 생각하기 어려워서 한참 고민하다가 서치를 통해 다른 사람의 풀이를 보고 해결한 것이다.

 

풀이를 보고도 이해가 잘 안되어서 직접 손으로 그려보기도 했다.

일단 먼저 생각해야 할 것이 정사각형이 되기 위한 조건이다.

왼쪽 윗대각선 , 왼쪽, 위 이렇게 세방향을 검사해주고 거기서 min+1값을 구하는 것이다.

왜 min값이어야 하는 가? min값으로 해야지 그 위치에서 만들 수 있는 최대 정사각형을 구할 수 있다.

그려보면 더 감이 올 것이다. 

 

말로 표현하기는 어렵지만 그려보는 것이 이해에 제일 도움이 되는 것 같다. 화이팅