[프로그래머스 동적계획법/DP]정사각형 찾기 - Python3

문제

https://programmers.co.kr/learn/courses/18/lessons/1879

알고리즘 문제 해설 - 가장 큰 정사각형 찾기 | 프로그래머스

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

예를 들어

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

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

 

알고리즘

def solution3(board):
    max_value = 0
    # 이 경우는, board의 모든 원소가 0인 경우 0을 리턴하기 위해서 만든 부분이다.
    for i in range(len(board)):
        max_value += sum(board[i][:])
    if max_value == 0:
        return 0

    #
    max_value = 0
    # i, j 두 인덱스를 통해서, board[1][1]부터 board의 마지막 원소까지 반복한다.
    for i in range(1, len(board)):
        for j in range(1, len(board[i])):
            # board[i][j]가 0이라면, continue한다.
            if board[i][j] == 0:
                continue

            # 그렇지 않다면, 위의 원소, 왼쪽 원소, 왼쪽 위의 원소 3가지를 비교한다.
            # 그리고 그 중 최소값을 뽑아서, 그 최소값에 1을 더한 값을 board[i][j]에 넣는다.
            else:
                min_value = min(board[i-1][j], board[i][j-1], board[i-1][j-1])
                board[i][j] = min_value + 1

                # 그리고, 최대값을 저장해두기 위해 board[i][j]가 나올 때마다 최대값인지 아닌지를 판단해서 저장한다.
                if max_value < board[i][j]:
                    max_value = board[i][j]

    if max_value == 0:
        return 1
    else:
        return max_value**2


board = [[0,1,1,1], [1,1,1,1], [1,1,1,1], [0,0,1,0]]
print(solution3(board))

설명

이 문제 역시 DP예제 3: 동전 줍는 로봇과 유사하다.

2020/01/30 - [공부/알고리즘] - [알고리즘 자습]동적계획법(Dynamic Programming) - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇

[알고리즘 자습]동적계획법(Dynamic Programming) - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇

한 원소의 왼쪽, 위쪽, 왼쪽위의 원소를 보면서, 해당 칸에 어떤 값을 넣을지를 결정하고, 그 중 최대값을 제곱해서 리턴한다. 이 과정을 좀더 구체적으로 보기 위해 그림을 통해 보자면

0	1	1	1
1	1	1	1
1	1	1	1
0	1	1	0

이렇게 초기 배열이 있을때, 

0	1	1	1
1	1	1	1
1	1	1	1
0	1	1	0

위에 주황색으로 색칠한 원소들은 고정해 두고, 연보라색으로 색칠한 부분은 반복을 통해 값을 갱신한다. 초기화와 반복에 범위에 대해 설명했다. 아래부터는 각 값을 어떻게 갱신할 지에 대해 쓰겠다. 

0	1	1	1
1	1	1	1
1	1	1	1
0	1	1	0

내가 원하는 것은, 각 원소의 값이 '현재 보고있는 원소 board[i][j]를 어떤 정사각형의 오른쪽 끝 꼭지점이라 할 때, 그 정사각형이 가질 수 있는 최대 변의 길이'를 가졌으면 좋겠다는 것이다. 그러기 위해서, 왼쪽, 위쪽, 왼쪽 위 원소들의 값을 보고, 그 최솟값을 뽑아서 그 최솟값에 1을 더한 값을 칸에 써넣는다. (1,1)의 원소가 어떻게 쓰여지는지 보면, 

색칠한 3가지 원소가 (1,1)을 결정하는데 영향을 준다. 이 중 최소값을 뽑아서 1을 더한 값을 집어넣으면 그대로 값은 1이 된다. 즉, (1,1)을 통해서 만들 수 있는 정사각형의 한 변의 길이는 1인 것이다. 다음번인 (1,2)를 보면, 

최솟값인 1에 1을 더한값을 집어 넣어, 그 값이 2가 된다. 즉, (1,2)를 정사각형의 오른쪽 끝 꼭지점이라 할 때, 만들 수 있는 정사각형의 한 변의 길이는 2라는 것이다. 이렇게 하면, (1,3)의 값을 다음과 같이 채워진다. 

 

이와 마찬가지로, 나머지 원소들 또한 반복을 거치고 나면 위 그림처럼 board가 완성된다. board의 원소중 최대값이 3이므로, 3의 제곱을 리턴한다. 

 

결과

올바른 결과를 출력한다. 

 

후기

코딩 테스트를 준비하던 초창기에 한번 보고 좌절했던 문제였는데, 공부를 다시 하다 생각이 나서 풀어봤다. 그랬더니 생각보다 쉽게 풀려서 기분이 너무 좋았다. 옛날에는 딴사람들 코드 보고 이걸 어케짰지 했는데, DP에 대한 이해, 값의 초기화와 점화식 등에 대한 활용 등을 알게 되니 마냥 어려운 문제는 아니었다. DP문제는 항상 초기와와 점화식 구성이 아이디어가 필요해서 어렵게 느끼는데, 그러한 아이디어 또한 예제에서 다룬 것을 크게 벗어나지 않았다.