Matrix - 가장 큰 정사각형 찾기

                                    ✍️ 시도한 방법
- BFS로 이미 차지된 영역 / 차지 되지 않은 영역에 대해 탐색을 시도했다.

                                    from collections import deque

def solution(mats, park):
    answer = 0

    # map 에서 가장 큰 n x n 영역 찾기
    # 좌, 우로만 확장해서 찾기

    empty_max = -999
    row = len(park)
    col = len(park[0])
    print(row, col)
    visited = [[0 for j in range(col)] for x in range(row)]
    print(visited)

    dx = [0, 1, 1]
    dy = [1, 0, 1]

    for i in range(row):
        for j in range(col):
            print("loop i, j", i, j)
            point = park[i][j]
            print("point: ", point, i, j)
            if visited[i][j] == 1:
                print("loop skip i, j", i, j)
                continue

            if point != "-1":
                # check Area
                visited[i][j] = 1
                print("i, j", i,j )

                area_que = deque([(i,j)])
                while area_que:
                    x, y = area_que.popleft()

                    for m in range(3):
                        nx, ny = x + dx[m], y + dy[m]

                        if nx < 0 or ny < 0 or nx >= row or ny >= row:
                            continue

                        if park[nx][ny] == "-1" or park[nx][ny] != point:
                            # end Area
                            print("nx, ny is empty", nx, ny)
                            continue

                        if visited[nx][ny] == 1:
                            continue

                        print("nx, ny is added to que : ", nx, ny)
                        area_que.append((nx, ny))
                        visited[nx][ny] = 1
            else:
                # empty
                print("empty !"i, j)

                empty_que = deque([(i,j)])
                size = 1
                while empty_que:
                    x, y = deque.popleft()

                    for m in range(3):
                        nx, ny = x + dx[m], y + dy[m]

                        if nx < 0 or ny < 0 or nx >= row or ny >= col:
                            continue

                        if park[nx][ny] != "-1":

                            continue

                        if

    print(visited)
    return answer

                                    ✍️ DP를 정의하기
- dp[i][j]는 (i,j)를 우하단 모서리로 하는 최대 정사각형

🖌️ 초기값
i = 0, j = 0은 1x1 정사각형 밖에 만들 수 없다.

🖌️ 판단
- i,j가 가질 수 잇는 최대 정사각형의 크기는 min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1 값이다.

🤔 이건 풀이방법을 모르면 풀 수 없는 문제였다.

                                    from collections import deque

def solution(mats, park):
    print(mats)
    R = len(park)
    C = len(park[0])
    matrix = [[1 if park[i][j] == "-1" else 0 for j in range(C)] for i in range(R)]
    dp = [[0]*C for _ in range(R)]
    max_len = 0

    # init set
    for r in range(R):
        dp[r][0] = matrix[r][0]

    for c in range(C):
        dp[0][c] = matrix[0][c]

    for i in range(1, R):
        for j in range(1, C):
            if matrix[i][j] == 0:
                dp[i][j] = 0
            else:
                dp[i][j] = min(
                  dp[i -1][j], dp[i -1][j -1], dp[i][j - 1]
                ) + 1

                max_len = max(max_len, dp[i][j])

    # adjust max_len
    answer = 0
    for mat in mats:
        if mat <= max_len:
            answer = max(mat, answer)

    return answer if answer != 0 else -1