[백준알고리즘] 1915번: 가장 큰 정사각형 -Python

[백준알고리즘] 1915번: 가장 큰 정사각형 -Python

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

이게 왜이리 오래 걸렸는지 모르겠다. 엄청 많이 틀렸다..

틀린 이유는 시간초과였는데, 결국 다른 풀이들을 찾아봤다.

 

처음에 시간 초과가 걸리게 푼 방법은 재귀 방식을 사용했다. 현재 위치를 정사각형의 왼쪽 위 꼭짓점이라고 생각을 하고 만들어지는 최대 정사각형의 변을 구했다.

다음 세개의 길이의 최솟값+1을 해줌으로써 현재 구할 수 있는 정사각형의 가장 큰 길이를 구했다.

1. 가로로 이어지는 길이
2. 세로로 이어지는 길이
3. (i+1, j+1)에서 재귀로 얻어낸 가장 큰 정사각형의 변의 길이

그리고 그 값을 또다른 이중 리스트를 만들어 길이를 기억하고 있도록 했다.

 

그래서 메모리도 괜찮았고, 2초에 1000x1000이라 생각해 시간도 괜찮게 돌아갈 줄 알았는데 아니었나 보다.

 

 

아무튼 구글링을 하니 대부분 아래와 같은 코드로 최대 길이를 구했다.

여기서는 (i, j)가 정사각형의 오른쪽 아래의 꼭짓점이라고 생각하고 반복문을 사용해 확장하나 가는 방법이다.

1. (i-1, j)에서 구할 수 있는 정사각형의 변의 최대 길이
2. (i-1, j-1)에서 구할 수 있는 정사각형의 변의 최대 길이
3. (i, j-1)에서 구할 수 있는 정사각형의 변의 최대 길이

이 값들 중 최솟값+1이 (i, j)에서 구할 수 있는 정사각형의 변의 최대 길이이다.

 

아이디어도 비슷하고 확장하는 방향과 재귀냐 반복문이냐 차이 같은데 역시 반복문이 빨라서 그런지 모르겠다.

 

코드는 @iknoom 님의 코드를 참조했습니다.

n, m = map(int, input().split())
table = [list(map(int, list(input().rstrip()))) for _ in range(n)]
ans = 0

for i in range(n):
    for j in range(m):
        if i>0 and j>0 and table[i][j] == 1:
            table[i][j] += min(table[i-1][j], table[i][j-1], table[i-1][j-1])
        ans = max(ans, table[i][j])
print(ans*ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다