[알고리즘/백준] 1915번 가장 큰 정사각형 Python 파이썬

 

이번 문제는 시간복잡도를 고려한 문제 DP 알고리즘이 필요한 문제였습니다.

 

 

배열이 주어졌을 때 최대 정사각형 넓이 구하는 문제로 단순하게 생각하면 반복문을 통해 검사해서 답을 구할 수 있지만 이 경우 시간초과가 날 수 있습니다. 이를 방지하기 위해서는 DP 알고리즘을 사용하여 시간 복잡도를 줄어야 통과가 될 수 있습니다. 

 

아래와 같은 코드로 통과하였습니다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
map_list = []
dp = [[0]*m for _ in range(n)]
for i in range(n):
    map_list.append(list(map(int, input().rstrip())))

answer = 0
for i in range(n):
    for j in range(m):
        if i == 0 or j == 0:
            dp[i][j] = map_list[i][j]
        elif map_list[i][j] == 0:
            dp[i][j] = 0
        else:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
        answer = max(dp[i][j], answer)

print(answer*answer)

 

위 풀이 방식에 대해 설명하자면, i, j 좌표가 주어졌을 때 [i-1][j-1] 칸과 [i-1][j]칸과 [i][j-1]칸중 가장 최소인 것의 +1이 해당 칸이 정사각형 오른쪽 아래 꼭짓점일 때 최대 크기의 정사각형임을 나타나는 규칙을 찾아서 적용시킨 풀이입니다.

 

아래는 시간 초과나서 안된 반복문을 통한 검사 코드입니다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
map_list = []
for i in range(n):
    map_list.append(list(map(str, input())))

def check_nemo(x,y):
    c = 2
    while True:
        check = 1
        for x1 in range(c):
            for y1 in range(c):
                if 0 <= (x+x1) < n and 0 <= (y+y1) < m:
                    if map_list[x + x1][y + y1] != '1':
                        check = -1
                else:
                    check = -1
        if check == -1:
            break
        else:
            c += 1
    return ((c-1)*(c-1))

answer = 0
for i in range(n):
    for j in range(m):
        if map_list[i][j] == '1':
            num = check_nemo(i,j)
            if num >= answer:
                answer = num
print(answer)

 

아직은 DP가 익숙하지 않아서 많이 헤매고 있는 것 같습니다. 언제쯤이면 스스로의 힘으로 문제들을 풀 수 있을지 갈 길이 먼 것 같네요...