[백준 1915] 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

---

접근

정사각형에서 오른쪽 맨 아래의 지점을 기준으로 왼쪽, 위, 대각선 위에서 최솟값을 구하고 그에 대한 +1을 오른쪽 맨 아래에 저장한다. 계속해서 누적해 나갔을 때 각각의 칸에는 한 변의 길이가 저장이되고 이 중 최댓값을 찾아 넓이를 구하면된다.

 

구현

- 입력 예시대로 입력을 받는다.

- 2차원 리스트인 memo에는 각 지점에서의 한 변의 길이가 저장된다.

- answer에 가장 긴 한 변의 길이가 저장된다.

N, M = map(int, input().split())
board = [list(map(int, input().strip())) for _ in range(N)]
memo = [[0 for _ in range(M)] for _ in range(N)]
answer = 0

- 해당 칸이 0일 때는 그대로 memo에 0을 넣는다. 정사각형이 성립이 되지 않기 때문이다.

- 이어서 0이 아닐 때는 왼쪽, 위, 왼쪽위 대각선을 비교하여 최솟값을 찾아 +1한 것을 memo에 저장한다.

- 이제 answer에 현재 위치에 저장된 길이와 비교하여 최댓값을 answer에 저장한다.

- 최종적으로 answer의 제곱이 최종해가 된다.

for y in range(N):
    for x in range(M):
        if y == 0 or x == 0:
            memo[y][x] = board[y][x]
        elif board[y][x] == 0:
            memo[y][x] = 0
        else:
            memo[y][x] = min(memo[y][x-1], memo[y-1][x], memo[y-1][x-1]) + 1
        answer = max(answer, memo[y][x])

---

전체 코드

N, M = map(int, input().split())
board = [list(map(int, input().strip())) for _ in range(N)]
memo = [[0 for _ in range(M)] for _ in range(N)]
answer = 0

for y in range(N):
    for x in range(M):
        if y == 0 or x == 0:
            memo[y][x] = board[y][x]
        elif board[y][x] == 0:
            memo[y][x] = 0
        else:
            memo[y][x] = min(memo[y][x-1], memo[y-1][x], memo[y-1][x-1]) + 1
        answer = max(answer, memo[y][x])

print(answer ** 2)