[프로그래머스] 가장 큰 정사각형 찾기

가장 큰 정사각형 찾기

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

입출력 예

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

입출력 예 설명
입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 |1|1|
| 1 | 1 |1|1|
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

풀이

• 실패한 풀이
  • 정답은 맞았으나 시간초과에서 걸림
• 사각형에서 값이 1인 원소를 모두 탐색하면서 생성할 수 있는 가장 정사각형 값을 추출
  • 정사각형 추출 방법
    • 1. row, col을 탐색하면서 1이 뻗어갈 수 있는 가장 최소의 값을 탐색 (row_cnt, col_cnt)
    • 2. for문을 이용해서 matrix의 row_cnt, col_cnt까지 만들 수 있는 정사각형 탐색
         • 1번째 for문의 i는 정사각형의 크기를 의미 (i = 1이면 크기 1의 정사각형)
         • 2, 3번째 for문은 행렬 내부의 원소를 탐색하려는 것을 의미

def findcandidates(board, row, col):
    col_cnt = 0
    row_cnt = 0

    # 오른쪽으로 가능한 1의 갯수 확인 
    for col_ in range(col, len(board[0])):
        if board[row][col_] == 1 : col_cnt += 1

    # 아래로 가능한 1의 갯수 확인 
    for row_ in range(row, len(board)):
        if board[row_][col] == 1 : row_cnt += 1    

    list_ = []
    for i in range(1, min(row_cnt, col_cnt)+1): 
    # 행렬의 원소의 최솟값이 1이 되는 최대의 i값을 확인
        flag_ = True
        for row_ in range(i):
            for col_ in range(i):
                if board[row+row_][col+col_] != 1:
                    flag_ = False
        if flag_ == True : list_.append(i)
    return max(list_)


def solution(board):
    answer = []
    # 아이디어 
    # 모든 원소를 돌아다니면서, 아래로 뻣어나가는 가장 큰 정사각형을 확인 
    for row in range(len(board)):
        for col in range(len(board[0])):
            if board[row][col] == 1: 
                answer.append(findcandidates(board, row, col))
    return max(answer) ** 2

수정된 풀이

• 런타임을 줄이기 위해서 두가지 트릭을 이용
  • 1. flag_가 False가 되면 그 이후의 정사각형은 탐색하지 않음
       • if flag_ == False : break
  • 2. answer의 max값보다 큰 정사각형을 만들 수 없는 부분은 탐색하지 않음
       • if (board[row][col] == 1) & (max(answer) <= len(board)-row) & (max(answer) <= len(board)-row)
• 하지만, 이래도 효율성 테스트에서는 실패

def findcandidates(board, row, col):
    col_cnt = 0
    row_cnt = 0

    # 오른쪽으로 가능한 1의 갯수 확인 
    for col_ in range(col, len(board[0])):
        if board[row][col_] == 1 : col_cnt += 1

    # 아래로 가능한 1의 갯수 확인 
    for row_ in range(row, len(board)):
        if board[row_][col] == 1 : row_cnt += 1    

    list_ = []
    flag_ = True
    for i in range(1, min(row_cnt, col_cnt)+1): 
    # 행렬의 원소의 최솟값이 1이 되는 최대의 i값을 확인
        if flag_ == False: break
        for row_ in range(i):
            for col_ in range(i):
                if board[row+row_][col+col_] != 1:
                    flag_ = False
        if flag_ == True : list_.append(i)
    return max(list_)


def solution(board):
    answer = [0]
    # 아이디어 
    # 모든 원소를 돌아다니면서, 아래로 뻣어나가는 가장 큰 정사각형을 확인 
    for row in range(len(board)):
        for col in range(len(board[0])):
            if (board[row][col] == 1) & (max(answer) <= len(board)-row) & (max(answer) <= len(board)-row): 
                answer.append(findcandidates(board, row, col))
    return max(answer) ** 2

수정된 풀이2

• Dp를 이용한 접근
• 크기2의 정사각형은 크기1의 정사각형에서 위, 대각선 왼쪽 위, 왼쪽이 붙으면 된다는 특성을 이용
  • i, j에 0이 포함되는 경우는 -1이 될 수 있으므로 계산 x
  • board[i][j]가 1인 경우에는 3가지 부분이 1인지 탐색
    • 위, 대각선 왼쪽 위, 왼쪽
    • 만약, 모두 1이면 board[i][j]를 2로 바꾸고 정사각형 크기2가 만들어 진다는 것을 의미

def solution(board):
    row = len(board)
    col = len(board[0])
    for i in range(row):
        for j in range(col):
            if i == 0 or j == 0:
                continue
            if board[i][j] != 0:
                board[i][j] = min(board[i-1][j-1],min(board[i-1][j],board[i][j-1]))+1
    answer=[]
    for i in range(row):
        answer.append(max(board[i]))
    return max(answer)**2