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

1. 문제

1915번: 가장 큰 정사각형

2. 개요

0, 1로 채워진 n x m 크기의 배열이 있다.

이 배열에서 1만으로 채워진 가장 큰 정사각형의 넓이를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

dp테이블을 만드는데, 이때 값은 해당 행 열을 오른쪽 아래 꼭짓점으로 하는 정사각형의 변의 최대 길이로 한다. 따라서 첫 행과 열에서 나올 수 있는 최댓값은 1이므로 board의 값을 그대로 따온다.

다음부터 dp의 1행 1열부터 탐색한다. board가 0이라면 정사각형을 만들 수 없으므로 넘어간다.

1이라면 왼쪽, 위쪽, 왼쪽 위 칸을 탐색한다. 이 중 가장 작은 값 + 1이 해당 칸의 최대 길이가 된다.

이 값과 answer을 계속 비교하면서 answer보다 크다면 값을 바꿔준다.

최종 답은 넓이이므로 구해진 answer를 제곱하여 답을 출력한다.

3-2. Python

import sys

n, m = map(int, sys.stdin.readline().split())

board = []
answer = 0

for i in range(n):
    k = list(map(int, list(sys.stdin.readline().rstrip())))
    if answer == 0 and 1 in k:
        answer = 1
    board.append(k)

dp = [[0 for _ in range(m)] for _ in range(n)]

for i in range(n):
    if i == 0:
        dp[i] = [b for b in board[0]]
    dp[i][0] = board[i][0]

for i in range(1, n):
    for j in range(1, m):
        if board[i][j] == 0:
            continue
        
        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

        if answer < dp[i][j]:
            answer = dp[i][j]

print(answer ** 2)

3-3. C#

internal class Program
{
    static string[] input;
    static void Main(string[] args)
    {
        int answer = 0;
        input = Console.ReadLine().Split();
        int n = int.Parse(input[0]);
        int m = int.Parse(input[1]);
        
        int[,] board = new int[n, m];
        int[,] dp = new int[n, m];

        for (int i = 0; i < n; i++)
        {
            input = Console.ReadLine().Split();
            for (int j = 0; j < m; j++)
            {
                board[i, j] = input[0][j] - '0';
                if (i == 0 || j == 0)
                {
                    dp[i, j] = input[0][j] - '0';
                    if (answer < dp[i, j])
                        answer = dp[i, j];
                }
            }
        }

        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < m; j++)
            {
                if (board[i, j] == 0)
                    continue;

                dp[i, j] = Math.Min(Math.Min(dp[i - 1, j], dp[i, j - 1]), dp[i - 1, j - 1]) + 1;
                if (answer < dp[i, j])
                    answer = dp[i, j];
            }
        }

        Console.WriteLine(answer * answer);

    }
}