가장 큰 정사각형 찾기

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

문제 설명

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

접근

우선 2차원 배열에서 첫 열부터 DFS처럼 아래로 내려가는 탐색을 진행한다. 여기서 처음 등장하는 1을 만난 순간부터 0을 만나기까지의 길이를 저장한다.

이렇게 하면 해당 열에서 만들 수 있는 최대 정사각형의 길이를 구한 셈이 된다.

그럼 옆 행으로 이동해 해당 길이를 만족할 수 있는지 알아낸다면 되지 않을까라고 생각했다.

물론, 이런 방식에는 여러 예외가 있고, 정답을 구하지 못하는 접근일 가능성이 크다 생각했다. 원래 한 번에 좋은 아이디어가 나오는 경우는 없지 않은가?

다른 사람의 해설

당연하게도 내가 막연히 생각한 방식을 어떻게 구현해야 할지 모르겠고, 맞는 방식인지도 모르겠다. 이렇게 막힐 때는 다른 사람의 도움을 받아야 한다고 생각한다.

그래서 검색을 한 결과 이번 문제는 DP를 적용시켜 푸는 문제라고 많은 사람들이 이야기하는 것을 봤다.

[Python] 프로그래머스. 가장 큰 정사각형 (Level 2) - 관찰과 질문 그리고 데이터

이 곳에 올라온 해설을 보니 정사각형에 대해 다음과 같은 규칙을 세울 수 있다고 한다.

• board[x][y] 값이 1일 때, 이 좌표 근처의 값을 확인해 정사각형인지를 확인할 수 있다.
  • board[x - 1][y] 값이 1인가? => 자신의 위
  • board[x][y - 1] 값이 1인가? => 자신의 왼쪽
  • board[x - 1][y - 1] 값이 1인가? => 자신의 대각선

(저 글에서는 위, 왼쪽, 대각선을 들었지만, 아래, 오른쪽 대각선을 사용할 수도 있고, 뭐, 검사하는 방식은 진행 방향에 따라 다를 것이다.)

DP하면 메모리제이션이니 이렇게 구해진 인덱스들을 어떻게 사용하긴 할 것이라 예상을 할 수 있다. 왜냐하면 이 경우는 2 X 2만 구할 수 있으니까.

[Programmers]Lv 2.가장 큰 정사각형 찾기 - CodeDrive - 티스토리

여기에 그림으로 설명해주셔서 메모리제이션을 사용하는 이유와 3 X 3을 찾는 방법을 알게 되었다.

그렇다면 이제 이 방식을 토대로 직접 구현해보고자 했다.

그렇게 구현한 코드

def solution(board):
    column = len(board[0])
    row = len(board)

    for y in range(1, column):
        for x in range(1, row):
            if board[x][y]:
                min_square_base = min(board[x][y - 1], board[x - 1][y - 1], board[x - 1][y])
                if min_square_base:
                    board[x][y] = min_square_base + 1

    max_square_base = 0

    for i in range(row):
        temp = max(board[i])
        if temp > max_square_base:
            max_square_base = temp

    return max_square_base ** 2

해결 과정

사실 위에 링크를 걸어놓은 두 개의 글을 보고 방식을 파악했으니 코드를 구현하는 것은 그렇게 어렵지 않았다.

내가 고려해야 할 부분은 그렇게 board 안에 있는 값을 바꿔 놓았을 때 문제에서 요구하는 답을 구하기 위해 어떻게 해야 하는가와 예외 상황에 대한 처리다.

정답을 구하는 방법

board 내에 있는 모든 요소에 값이 있을 것이고, 그 값들 중 가장 큰 값을 구하면 board에서 만들 수 있는 가장 큰 정사각형의 한 변의 길이를 구하게 된다.

정사각형의 넓이를 반환하는 것이므로 위에서 구한 값을 제곱하여 반환하면 문제를 해결할 수 있다.

예외 - 0으로만 이루어진 board

이 경우는 반복문을 돌때 if board[x][y]에 의해 걸러지기 때문에 밑에 연산이 수행되지 않는다.

그리고 답은 0을 반환해야 하는데, 이 부분도 반복문을 돌더라도 최댓값이 0이기 때문에 결국 0이 구해지고 0의 제곱은 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

위에 링크를 걸어둔 [Python] 프로그래머스. 가장 큰 정사각형 (Level 2) - 관찰과 질문 그리고 데이터에 게시되어 있던 코드다.

return 문을 라이브러리를 사용하여 한 줄로 구현했다는 점이 내 풀이와 다른 점이다.

itertools.chain.from_iterable은 2차원 배열을 하나의 배열로 묶어주는 기능을 수행한다. 다만 list로 반환하는 것이 아니므로 list로 묶을 필요가 있다.

자세한 내용은 R, Python 분석과 프로그래밍의 친구 (by R Friend)를 읽어보면 알 수 있다.