[Python/파이썬] 백준 4095번 최대 정사각형

4095번: 최대 정사각형

 

코드

import sys
input = sys.stdin.readline

while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    matrix = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0]*(m+1) for _ in range(n+1)]
    ans = 0
    for i in range(1, n+1):
        for j in range(1, m+1):
            if matrix[i-1][j-1] == 1:
                dp[i][j] = min([dp[i-1][j], dp[i-1][j-1], dp[i][j-1]])+1
            if dp[i][j] > ans:
                ans = dp[i][j]
    print(ans)

 

dp배열에 (i, j)번째 칸까지 만들 수 있는 정사각형 한 변의 길이를 저장한다.dp 배열에 값을 채워넣을 때는 왼쪽, 대각선 왼쪽 위, 위쪽 칸의 dp 값 중 가장 작은 값+1을 해주면 된다. 왜냐하면 3방향 중 어느 쪽이라도 0이 있어서 비는 부분이 있다면 정사각형이 완성될 수 없기 때문이다.

 

 

아래는 처음에 시도했던 코드이다. PyPy3로는 통과되지만 Python3로는 시간초과가 발생한다.

import sys
input = sys.stdin.readline

while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    matrix = [list(map(int, input().split())) for _ in range(n)]
    dp = [[[0, 0] for _ in range(m)] for _ in range(n)]
    ans = 0
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                if i == 0 and j > 0:
                    dp[i][j] = [1, dp[i][j-1][1]+1]
                elif i > 0 and j == 0:
                    dp[i][j] = [dp[i-1][j][0]+1, 1]
                else:
                    dp[i][j] = [min(dp[i-1][j][0], dp[i-1][j-1][0])+1,
                                min(dp[i][j-1][1], dp[i-1][j-1][1])+1]
            if matrix[i][j] != 0 and dp[i][j][0] == dp[i][j][1]:
                ans = max(ans, dp[i][j][0])
    print(ans)

위 코드와 다른 점은

1. dp 배열에 정사각형 한 변의 길이가 아닌 해당 칸까지 만들 수 있는 직사각형의 가로세로 길이를 모두 저장했다.
2. dp 배열을 (n+1)×(m+1)로 만들지 않고 n×m으로 만들어서 0행, 0열일 때를 따로 조건문으로 구해주어서 코드가 길어졌다.

이걸 고쳐서 위의 코드로 만드니 Python3로도 통과가 됐다.