가장 큰 정사각형 [JAVA] (백준 1915)

 

문제

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

1937번: 욕심쟁이 판다

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	23233	7176	5139	29.287%

문제

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

0100
0111
1110
0010

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

입력

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

출력

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

 

풀이

처음에는 어렵게 생각해서 여러 함수를 짰는데, 의외로 간단한 문제였다.

지점A에서 정사각형이 되려면, A를 기준으로 →↓↘ 가 정사각형을 만족하면 된다.

이를 만족하는 점들의 값을 계속해서 저장해주면 되는데,

체크한 점들의 최소값을 더하는 방식으로 구현하면 된다.

이때 진행방향은 지점A가 다음번 점의 검사에 포함될 수 있도록 조정하면 된다.

 

코드

import java.io.IOException;
import java.util.StringTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;


public class Main {

    static int n;
    static int m;
    static int[][] map;

    public static void main(String[] args) throws IOException{
        StringTokenizer st;
        BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n+1][m+1];

        for(int i=0; i<n; i++) {
            String[] s = br.readLine().split("");
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(s[j]);
            }
        }

        int answer = 0; {
            for(int y=n-1; y>=0; y--) {
                for(int x=m-1; x>=0; x--) {
                    if(map[y][x] == 1) {
                        int min = Math.min(map[y+0][x+1], map[y+1][x+0]);
                        map[y][x] += Math.min(min, map[y+1][x+1]);
                    }
                    answer = Math.max(answer,map[y][x]);
                }
            }
        }
        System.out.println(answer*answer);

    }
}

 

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!