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

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

1915번: 가장 큰 정사각형

 

문제 이해

 

주어진 2-dimension array에서 가장 큰 정사각형의 넓이를 구해주는 문제이다.

 

문제에서 주어진 예시에서 가장 큰 정사각형의 넓이는 2 x 2 = 4라고 할 수 있다.

 

 

그럼 과연, 알고리즘적으로 어떻게 설계해야 가장 큰 정사각형을 찾을 수 있을까?

 

일단 아래와 같이 해당 이중배열에서, 특정 원소를 M(i, j) 라고 해주자.

 

그럼 아래와 같은 점화식을 통해서, 가장 큰 정사각형의 한 변의 길이를 찾을 수 있다.

 

[ 단, 아래의 점화식은 M(i,j) 가 0이 아닐 때 만족한다. ]

 

첫 번째 그림에서는, M(1,1)을 기준으로 점화관계를 살펴보면, 

 

가장 큰 정사각형의 한변의 길이는 1이라는 것을 알 수 있다.

 

두 번째 그림에서는 가장 큰 정사각형의 한 변의 길이는 2라는 것을 알 수 있다.

 

위의 점화관계식을 거치고 난후 각 배열의 원소들은 해당 값으로 변경해줘야 한다.

 

두 번째 그림의 점화관계를 계산한 후 M(2,2)의 값은 아래와 같이 2로 수정된다.

 

 

혹시 위의 설명에도 아직 이해가 안되었다면,

 

좀 더 디테일한 시나리오를 가지고 이해해 보자.

 

 

아래와 같은 이중배열이 있다고 가정해 보자.

 

해당 이중배열에서 가장 큰 정사각형의 넓이는 몇일까?

계산결과는 아래와 같다.

그러므로 해당 이중배열에서 가장 큰 정사각형의 한 변의 길이는 3이 되고,

 

해당 정사각형의 넓이는 3 x 3 = 9가 된다.

 

그럼 위의 로직을 사용해서 코드를 구성해 보자.

 

일단 C++를 통한 코드 구성이다.

 

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

using namespace std;

int N,M;
int map[1000][1000];

int main()
{
    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        string inputs;
        cin >> inputs;

        for (int j = 0; j < M; j++)
        {
            map[i][j] = inputs[j] - '0';
        }
    }

    int max_len = 0;

    for (int i = 1; i < N; i++)
    {   
        for (int j = 1; j < M; j++)
        {
            if (map[i][j] != 0)
            {
                map[i][j] = min(map[i-1][j-1], min(map[i-1][j], map[i][j-1])) + 1;
                max_len = max(max_len, map[i][j]);
            }
        }
    }

    cout << max_len * max_len << endl;

    return 0;
}

위와 같이 문제에서 제시된 예시값을 넣어본 결과.

 

같은 결과가 나온다. 그래서 백준에 해당 코드를 제출해 보았다.

 

하지만, 돌아오는 것은... 틀렸다는 메시지였다.

 

로직이 틀린 것은 없는데, 이유가 뭘지 곰곰이 생각해 보았다.

 

그렇게 찾아낸 반례는 아래와 같다.

 

딱, 1 만 있는 경우에 가로 세로의 길이가 1인 정사각형을 만족하기 때문에,

 

최대 정사각형의 크기는 1이 되어야 하지만,

 

해당 코드를 컴파일해서 결과를 보면 0으로 결과가 나오는 걸 볼 수 있다.

 

해당 결과가 나오는 이유는 아래와 같은 영역만 계산해 줬기 때문이다.

즉, M(0,0)부터 계산해줘야 하는데,

 

이렬 경우 배열의 인덱스 범위를 초과하기 때문에, 아래와 같이 배열을 재 구성해줘야 한다.

 

위와 같이 배열을 재 구성해 준다면,

 

인덱스 범위를 초과하지 않고, M(0,0)부터 계산이 가능해진다.

 

 

배열 재구성을 통한 풀이

 

1. C++

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

using namespace std;

int N,M;
int map[1010][1010];

int main()
{
    cin >> N >> M;

    for (int i = 1; i <= N; i++)
    {
        string inputs;
        cin >> inputs;

        for (int j = 0; j < M; j++)
        {
            map[i][j+1] = inputs[j] - '0';
        }
    }

    int max_len = 0;

    for (int i = 1; i <= N; i++)
    {   
        for (int j = 1; j <= M; j++)
        {
            if (map[i][j] != 0)
            {
                map[i][j] = min(map[i-1][j-1], min(map[i-1][j], map[i][j-1])) + 1;
                max_len = max(max_len, map[i][j]);
            }
        }
    }

    cout << max_len * max_len << endl;

    return 0;
}

 

 

2. JAVA

import java.io.*;
import java.util.*;

public class Main {
    static int N,M;
    static int[][] map;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        
        map = new int[N+1][M+1];

        for (int i = 1; i <= N; i++) {
            String[] inputs = br.readLine().split("");

            for (int j = 0; j < M; j++) {
                map[i][j+1] = Integer.parseInt(inputs[j]);
            }
        }   

        int maxCnt = 0;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] != 0) {
                    map[i][j] = Math.min(map[i-1][j-1], Math.min(map[i-1][j], map[i][j-1])) + 1;
                    maxCnt = Math.max(maxCnt, map[i][j]);
                }
            }
        }

        bw.write(maxCnt*maxCnt + "");
        bw.close();
        br.close();
    }
}

 

 

3. Python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
map = [[0] * (M + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    inputs = list(input().strip())
    for j in range(M):
        map[i][j + 1] = int(inputs[j])

max_cnt = 0

for i in range(1, N + 1):
    for j in range(1, M + 1):
        if (map[i][j] != 0):
            map[i][j] = min(map[i-1][j-1], min(map[i-1][j], map[i][j-1])) + 1
            max_cnt = max(max_cnt, map[i][j])

print(max_cnt*max_cnt)

 

 

물론 위와 같이 배열 재 구성 없이 코딩해주는 방법도 존재한다.

 

배열 재구성 없는 풀이

 

1. C++

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

using namespace std;

int N,M;
int map[1000][1000];

int main()
{
    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        string inputs;
        cin >> inputs;

        for (int j = 0; j < M; j++)
        {
            map[i][j] = inputs[j] - '0';
        }
    }

    int max_len = 0;

    for (int i = 0; i < N; i++)
    {   
        for (int j = 0; j < M; j++)
        {
            if (map[i][j] != 0)
            {
                int i_m = i - 1;
                int j_m = j - 1;
                
                int map_im_jm = (i_m < 0 || j_m < 0) ? 0 : map[i-1][j-1];
                int map_im_j = (i_m < 0) ? 0 : map[i-1][j];
                int map_i_jm = (j_m < 0) ? 0 : map[i][j-1];

                map[i][j] = min(map_im_jm, min(map_im_j, map_i_jm)) + 1;
                max_len = max(max_len, map[i][j]);
            }
        }
    }

    cout << max_len * max_len << endl;

    return 0;
}

 

 

2. JAVA

import java.io.*;
import java.util.*;

public class Main {
    static int N,M;
    static int[][] map;
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        
        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            String[] inputs = br.readLine().split("");

            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(inputs[j]);
            }
        }   

        int maxCnt = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    
                    int im = i - 1;
                    int jm = j - 1;

                    int mapImJm = (im < 0 || jm < 0) ? 0 : map[i-1][j-1];
                    int mapImJ = (im < 0) ? 0 : map[i-1][j];
                    int mapIJm = (jm < 0) ? 0 : map[i][j-1];
                    
                    map[i][j] = Math.min(mapImJm, Math.min(mapImJ, mapIJm)) + 1;
                    maxCnt = Math.max(maxCnt, map[i][j]);
                }
            }
        }

        bw.write(maxCnt*maxCnt + "");
        bw.close();
        br.close();
    }
}