[ Baekjoon - 11/10 ] - 1915번: 가장 큰 정사각형

• 문제 링크 : https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

• 소요 시간 : 1시간 50분

가장 큰 정사각형

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

32851

9763

7039

29.355%

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

예제 입력 1 복사

4 4
0100
0111
1110
0010

예제 출력 1 복사

4

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 128MB
   • 문제
     
     • N x M의 지도(1 ≤ N, M ≤ 1,000), 지도의 칸들은 0또는 1을 가짐
     • 위 지도에서 1로 만들 수 있는 가장 큰 정사각형을 찾아서 해당 사각형의 넓이를 출력하는 문제
     • 문제조건이 너무 아쉬웠는데, 여기서 정사각형은 행과 평행한 가로와 열과 평행한 세로를 변으로 가지고, 1로 모든 면이 꽉 차있는 형태를 말하는 것 같다.. (질문하기 보고 얻은 정보들..)
   • 이해
     • 문제이해가 어려운 문제는 아니었으므로 생략, 구현은 바로 떠오르지 않았지만 ㅠ
2. 문제를 익숙한 용어로 재정의와 추상화
   • 입출력 양식에 따라 끄적인게 전부라 생략
3. 문제를 어떻게 해결할 것인가

   • 

      
   • 1st 접근 - 정사각형의 특징을 생각해 얻은 솔루션...이지만 실상 노가다)
     • 가로와 세로가 행,열과 평행해야하는 정사각형이므로, 
       각각 가로와 세로 리스트에 연속된 1의 길이를 합산하면 정사각형이 가능한 길이인지 아닌지를 걸러낼 수 있다고 생각했다.
     • 길이가 1이라는건 한칸에 1있는 것이므로, 모든 칸에 0이 아니라면 존재하므로 2부터 따져보았다.
     • 2의 경우, 가로 2줄 세로 2줄이므로 합했을때 4가 나와야하고,
       3의 경우, 가로 3줄 세로 3줄이므로 합하면 6
       4의 경우, 가로 4줄 세로 4줄이므로 합하면 8.... 이기 때문에
       각 인덱스 * 2한 값보다 큰값이라면 해당 길이를 가진 정사각형을 따져보면 된다고 생각했다.
     • 하지만, 해당 길이 찾는 반복부터, 찾고나서도 맵을 반복해야하므로 시간이 매우 안타까웠다..
     • 그래서 다른 솔루션을 생각해보았다.
   • 2nd 접근 - dp문제였다니...ㅠ)
     • 문제를 따져보았을때 전혀 감이 잡히지가 않아서 알고리즘 분류를 보니 dp였다..
     • 이걸 어떻게 dp로 담을 점화식은 뭔지, 점화식을 찾기위해선 규칙을 찾아야하는데 규칙이 뭔지 전혀 모르겠어서.. 결국 다른 사람들의 해답을 참고하여 작성했다ㅠ
     • 정사각형을 찾았을때의 기준으로, 오른쪽 하단 꼭짓점 좌표에 현재 만들 수 있는 정사각형 한변의 길이를 기록하는 방식으로 접근하면 풀 수 있다!
     • (x,y)가 현재 좌표이고, (x-1,y-1), (x,y-1), (x-1,y)가 맵안이라 가정해보면,
       현재 좌표가 아닌 나머지 3개의 좌표는 이때까지 만들 수 있는 가장 큰 정사각형 한변의 길이를 저장하고 있을 것이다. (x,y)의 지도 좌표가 1이라면 한칸 더 이어진 정사각형을 만들 수 있을 것인데 어디서 한칸 늘어난 정사각형인지 생각해볼 필요가 있다.
     • 답부터 말하면 세 좌표중 가장 작은값이다. 최댓값이 가능했다면, 위 3개의 좌표가 다 최댓값을 가지고 있다는 소리이기 때문에.
     • 이를 이용해 코드를 작성해보았다!
4. 위 계획을 검증
   • 전 과정에서 만들 수 있는 정사각형의 한변의 길이를 저장하며 갱신하는 방식이므로, 조건문에 오류가 없다면 무난히 실행될 수 있다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main {
            static int N, M, ans;
            static int[][] map, dp;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
                StringTokenizer st = new StringTokenizer(br.readLine());
                N = Integer.parseInt(st.nextToken());
                M = Integer.parseInt(st.nextToken());
        
                map = new int[N][M];
                dp = new int[N][M];
                for (int n = 0; n < N; n++) {
                    String str = br.readLine();
                    for (int m = 0; m < M; m++) {
                        map[n][m] = Integer.parseInt(str.charAt(m)+"");
                        dp[n][m] = map[n][m];
                        // 해당 좌표가 1이고, 왼쪽 위쪽 좌표가 맵안, 값이 0보다 크면 갱신가능
                        if(n>=1 && m>=1 && dp[n-1][m-1]>0 && dp[n-1][m]>0 && dp[n][m-1]>0 && dp[n][m]>0){
                            // 왼,위,현재 좌표의 최솟값이 전 좌표들에서 만들 수 있던 가장 큰 정사각형이므로 +1
                            dp[n][m] = Math.min(dp[n-1][m], Math.min(dp[n-1][m-1], dp[n][m-1]))+1;
                        }
                        ans = Math.max(ans, dp[n][m]);
                    }
                }
                bw.write((ans*ans)+"\n");
                bw.flush();
            }
        }

   2. Python 3

      • import sys
        # sys.stdin = open("input.txt")
        input = sys.stdin.readline
        
        def solution():
            ans = 0
            for n in range(N):
                for m in range(M):
                    dp[n][m] = board[n][m]
                    # n-1과 m-1이 맵안이고, 좌측상단, 위쪽, 좌측, 현재 dp값이 0보다 크다면
                    if n >= 1 and m >= 1 and dp[n - 1][m - 1] > 0 and dp[n - 1][m] > 0 and dp[n][m - 1] > 0 and dp[n][m] > 0:
                        # 왼,위,현재 좌표의 최솟값이 전 좌표에서 만들 수 있던 가장 큰 정사각형이므로 +1 
                        dp[n][m] = min(dp[n - 1][m], dp[n - 1][m - 1], dp[n][m - 1]) + 1
                    ans = max(ans, dp[n][m])
            print(ans * ans)
        
        if __name__ == "__main__":
            N, M = map(int, input().split())
            board = [list(map(int, input().rstrip())) for _ in range(N)]
            dp = [[0] * M for _ in range(N)]
            solution()

 

• 결과

처음 틀렸습니다는 조건을 잘못 세워서 생긴 문제이고, 두번째는 ans를 구하는 부분을 if문 안으로 넣어버려서 생긴 문제이다. ans 디폴트값을 1로 잡고가면 괜찮을거라 생각해서 낸 제출이었는데, 아직까지도 어느 케이스에서 오류인지 잘 모르겠긴하다..