[BOJ 1915] 가장 큰 정사각형(C++)

가장 큰 정사각형(Gold4)

문제

전체 문제 보기

1915번: 가장 큰 정사각형

접근법

처음 문제에 접근할 때 완전 탐색이 가능한지 먼저 확인해보는 것이 중요합니다. 임의의 위치 \((r, c)\)에서 만들 수 있는 정사각형의 최대 크기를 탐색해보기 위해서는 \(O(n^4)\)의 계산량이 필요합니다. 아쉽게도 이번 문제에서는 \(n\)의 크기가 최대 \(1,000\)이기 때문에 완전 탐색으로는 풀 수 없는 문제입니다.

 

이번 문제는 동적계획법을 활용한 최적화가 필요합니다. 동적 계획법으로 풀기 위해서 점화식을 다음과 같이 세울 수 있습니다.

// dp[r][c]: r,c 위치에서 만들어지는 정사각형의 한 변의 길이
for (int r = 1; r < n; r++)
{
    for (int c = 1; c < m; c++)
    {
        if (dp[r][c] != 0)
        {
            dp[r][c] += std::min({ dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1] });
        }
    }
}

이때 dp[r][c]가 0인 경우는 정사각형을 만들 수 없기 때문에 그대로 0을 유지해야 합니다. 이렇게 구한 정사각형 한 변의 길이 중 가장 큰 값을 탐색한 후 제곱하여 너비를 출력함으로써 답을 구합니다.

int answer{};

for (int r = 0; r < n; r++)
    for (int c = 0; c < m; c++)
        answer = std::max(answer, dp[r][c]);

answer *= answer;
std::cout << answer << std::endl;

전체 소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
    //입출력 성능향상을 위한 설정
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(NULL);
    std::cin.tie(NULL);

    int n, m; //  n, m(1 ≤ n, m ≤ 1,000)
    std::cin >> n >> m;
    std::vector<std::vector<int>> dp(n, std::vector<int>(m,0));
    for (int r = 0; r < n; ++r)
    {
        std::string str;
        std::cin >> str;
        for (int c = 0; c < m; ++c)
        {
            dp[r][c] = (int)(str[c] - '0');
        }
    }

    // dp[r][c]: r,c 위치에서 만들어지는 정사각형의 한 변의 길이
    for (int r = 1; r < n; r++)
    {
        for (int c = 1; c < m; c++)
        {
            if (dp[r][c] != 0)
            {
                dp[r][c] += std::min({ dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1] });
            }
        }
    }

    int answer{};

    for (int r = 0; r < n; r++)
        for (int c = 0; c < m; c++)
            answer = std::max(answer, dp[r][c]);

    answer *= answer;
    std::cout << answer << std::endl;
    return 0;
}

실행 결과