프로그래머스 Lv.2) 가장 큰 정사각형 찾기

가장 큰 정사각형 찾기

코딩테스트 연습 - 가장 큰 정사각형 찾기

풀이

DP를 이용해 이 문제를 풀었다. Top-down을 이용해서 풀었고, board를 돌면서 어떠한 점이 1이라면 그 점을 기준으로 왼쪽, 왼쪽 상단, 상단 세 점의 최소값을 찾아 1을 더해줬다. 이후에 max값을 갱신했고, 탐색이 끝난 후에는 max값의 제곱을 리턴해주었다.

 

1. board의 모든 점을 탐색한다.

2. board가 1이라면 해당 점을 기준으로 좌측, 좌측 상단, 상단 세 점의 최소값을 찾는다.

 2.1 최소값에 +1을 해주어 해당 점에서 만들 수 있는 정사각형의 최대 크기를 저장해주었다.

3. 2번이 끝난 후 max를 갱신해주면서 답을 찾았다.

4. 넓이를 return 해야해서 제곱값을 리턴해주었다.

 

코드

public class FindMaxSquare_12905 {
    final static int[] dx = {-1,0,-1};
    final static int[] dy = {-1,-1,0};

    private static int solution(int [][]board) {
        int answer =0;
        int yLen = board.length;
        int xLen = board[0].length;

        if(yLen ==1 || xLen ==1) {
            loop :
            for(int[] line : board) {
                for(int num : line) {
                    if(num ==1) {
                        answer =1;
                        break loop;
                    }
                }
            }
        } else {
            for(int y=1; y<yLen; y++) {
                for(int x=1; x<xLen; x++) {
                    if(board[y][x]==1) {
                        int min = 1000;
                        for(int i=0; i<3; i++) {
                            int ny = y+dy[i];
                            int nx = x+dx[i];
                            min = Math.min(board[ny][nx], min);
                        }
                        board[y][x] = min+1;
                        answer = Math.max(board[y][x], answer);
                    }
                }
            }
        }

        return (int)Math.pow(answer,2);
    }
    public static void main(String[] args) {
        int[][] board = {{0,1,1,1},{1,1,1,1},{1,1,1,1},{0,0,1,0}};
        System.out.println(solution(board));
    }
}