[Algorithm]Baekjoon 1915 :: 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

 
int n, m;
int arr[1001][1001] = { 0 };
int dp[1001][1001] = { 0 };
int answer = 0;
 
int DFS(int leftTopY, int leftTopX)
{
    if (arr[leftTopY][leftTopX] == 0) return 0;
    if (dp[leftTopY][leftTopX] != 0) return dp[leftTopY][leftTopX];
    if (leftTopY < 0 || leftTopY == n || leftTopX < 0 || leftTopX == m) return 0;
 
    int a = DFS(leftTopY + 1, leftTopX+1);
    int b = DFS(leftTopY + 1, leftTopX);
    int c = DFS(leftTopY, leftTopX + 1);
 
    answer = max(answer, dp[leftTopY][leftTopX] = min(a, min(b, c)) + 1);
 
    return dp[leftTopY][leftTopX];
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
 
        for (int j = 0; j < m; ++j)
        {
            arr[i][j] = s[j] - '0';
            if (arr[i][j] == 1) answer = 1;
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (arr[i][j] == 0) continue;
            if (dp[i][j] != 0) continue;
 
            DFS(i, j);
        }
    }
 
    cout << answer * answer;
}
 
 
 

 

일단 재귀함수형식으로 풀었다. 1인값을 시작으로, 우측아래방향으로 계속 파고들다가 결국 arr의 우측아래에서부터 값을 업데이트하면서 끌고 올라오는 방식이다.

다만 재귀보다는 for문으로 하는게 함수호출과정이 없기때문에 수행속도가 더 빠르다.

근데 머리속에 전개되는건 일단 재귀함수방식이 더 잘그려지기 때문에 어지간하면 일단 이걸로 풀고, 이후에 for문으로 바꾸던가 할듯하다.

실제 코테때는 재귀방식이든 for문방식이든 dp개념 잘 적용했으면 둘 다시간제한에 걸리지는 않을것이다.

아래는 반복문으로 푼 코드.

 

int n, m;
int arr[1001][1001] = { 0 };
int dp[1001][1001] = { 0 };
int answer = 0;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
 
        for (int j = 0; j < m; ++j)
        {
            arr[i][j] = s[j] - '0';
            if (arr[i][j] == 1) answer = 1;
        }
    }
 
    for (int i = n-2; i >= 0; --i)
    {
        for (int j = m-2; j >= 0; --j)
        {
            if (arr[i][j] == 0) continue;
 
            answer = max(answer,arr[i][j] = min(arr[i + 1][j + 1], min(arr[i + 1][j], arr[i][j + 1])) + 1);
        }
    }
 
    cout << answer * answer;
}
 
 
 

 

시간비교

 

 

32ms가 재귀, 12ms가 반복문이다.