[LeetCode]Maximal Square

https://leetcode.com/problems/maximal-square/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 이차원 Matrix에서 가장 큰 정사각형에 포함된 1의 갯수를 구하는 문제입니다.

 

처음 시도한 답안 - 실패

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        ans = 0
        
        for i in range(m):
            for j in range(n):
                count = 0
                if matrix[i][j] == '1':
                    x = i + 1
                    y = j + 1
                    count = 1
                    flag = False
                    # print(i,j, "i J")

                    while x < m and y < n and not flag:
                        # print(x, y, "While")
                        # count += 1

                        for xx in range(x-i+1):
                            # print(i,j, "i, j", x,y, "x,y", xx, y, "xx, y")
                            if matrix[xx+i][y] == '0':
                                # print(xx,y, flag, "Flag 1")
                                flag = True

                        for yy in range(y-j+1):
                            # print(i,j, "i, j", x,y, "x,y", x, yy, "x, yy")
                            if matrix[x][yy+j] == '0':
                                # print(x,yy, flag, "Flag 2")
                                flag = True

                        if not flag:
                            count += 1

                        x += 1
                        y += 1

                    # print(count, "Count")

                ans = max(ans, count)

        return ans * ans

접근 방법

1. 등장한 i,j 에서 오른쪽 아래로 길이를 1씩 증가하면서 정사각형의 탐색 범위를 늘려나가는 방식입니다.
2. Matrix를 이중 순회합니다.
   1. 내부 반복문을 통해서 정사각형의 길이를 1씩 증가시키면서 그 안에 숫자가 모두 1인지를 판단합니다.
   2. count한 수중 최대치를 기록합니다.

처음에는 이차원 Matrix를 순회하면서 오른쪽 아래 방향으로 정사각형을 확장시키면서 모두 1이 포함된 정사각현인지 풀이하고자 했습니다. 대부분의 테스트 케이스는 맞출 수 있었지만, Matrix가 커질수록 오래 걸리는 시간복잡도이기에 Time Limit Exceeded로 해결할수는 없었습니다. 

그래서 DP를 활용한 다른 솔루션을 참고해 풀이했습니다.

 

두번째로 시도한 답안

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        ans = 0

        # dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "1":
                    if i == 0 or j == 0:
                        ans = max(1, ans)

                    else:
                        matrix[i][j] = min(int(matrix[i-1][j-1]), int(matrix[i][j-1]), int(matrix[i-1][j])) + 1
                        ans = max(ans, matrix[i][j])

        return ans * ans

접근 방법

1. DP를 활용한 풀이입니다.
2. Matrix를 이중 순회합니다.
   1. 만약 등장한 숫자가 1이라면
      1. 첫번째 열이거나 첫번째 행이라면, 1과 ans중 큰 값을 고르고 ans를 갱신합니다.
         1. 첫번째 열과 행에서는 가장 큰 정사각형은 길이가 1이기 때문입니다.
      2. 첫번째 열이나 행이 아니라면, (i-1, j-1), (i, j-1), (i-1, j) 중에서 작은 값 + 1을 더하고 ans를 갱신합니다.
3. 이중 순회를 완료하고 가장 큰 ans를 제곱하여 리턴합니다.

 

이 풀이방식의 경우 길이가 2인 정사각형을 움직이면서 값을 찾아가는 방식입니다. 예시를 통해 살펴보겠습니다.

 

아래와 같은 숫자에서, (2,2) 지점이 (i, j)로 등장한 경우에는 min(1, 0, 1) + 1 = 2가 (2,2)에 기록됩니다.

1	0
1	1

 

아래와 같은 숫에서, (2,2) 지점이 (i, j)로 등장한 경우에는 min(0, 0, 0) + 1 = 1이 (2,2)에 기록됩니다.

0	0
0	1

 

다음과 같은 배열이 인풋으로 주어진다면

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

 

DP를 수행한 결과는 아래와 같이 됩니다.

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

 

DP에서 등장한 가장 큰 숫자인 3 * 3 = 9가 정답이 됩니다.