programmers_가장 큰 정사각형 찾기_java

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

 

- 완전탐색 : 효율성 시간초과

import java.util.*;

class Solution
{
    private static int[][] delta = {{0,1}, {1, 0}, {1,1}}; // 우, 하, 우하

    public int solution(int [][]board){
        int answer = 0;

        int width = board[0].length;
        int hieght = board.length;

        for (int i = 0; i< hieght; i++){
            for (int j = 0; j<width; j++){
                if(board[i][j] == 1){ // 1인 좌표에서 사각형 탐지
                    answer = Math.max(findSquare(width, hieght, board, i, j), answer);
                }
            }
        }

        return answer * answer;
    }

    public int findSquare(int width, int height, int[][] board, int y, int x){
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(y, x));
        boolean[][] visited = new boolean[height][width];
        int level = 1;

        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i<size; i++){
                Point nowPoint = queue.poll();

                if (visited[nowPoint.y][nowPoint.x]) continue;
                visited[nowPoint.y][nowPoint.x] = true;
                
                for (int j = 0; j<3; j++){
                    int nexty = nowPoint.y + delta[j][0];
                    int nextx = nowPoint.x + delta[j][1];
                    if (0<=nexty && nexty<height && 0<=nexty && nextx <width && board[nexty][nextx] == 1){
                        queue.offer(new Point(nexty, nextx));
                    }else{
                        return level;
                    }
                }
            }
            level++;
        }

        return level;
    }

    public class Point{
        int y, x;
        public Point(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
}

 

- dp

import java.util.*;

class Solution
{
    private static int[][] delta = {{0,-1}, {-1, 0}, {-1,-1}}; // 좌, 상, 좌상

    public static int solution(int [][]board){
        int answer = 0;

        int width = board[0].length;
        int height = board.length;
        int[][] dp = new int[height][width];

        for (int i = 0; i< height; i++){
            for (int j = 0; j<width; j++){
                if(board[i][j] == 1){
                    dp[i][j] = isSquare(width, height, dp, i, j) + 1;
                    answer = Math.max(answer, dp[i][j]);
                }
            }
        }
//        // dp 배열 확인용
//        for (int i = 0; i< height; i++){
//            for (int j = 0; j<width; j++){
//                System.out.print(dp[i][j] + " ");
//            }
//            System.out.println();
//        }

        return answer * answer;
    }

    public static int isSquare(int width, int height, int[][] dp, int y, int x){
        int res = Integer.MAX_VALUE;

        boolean suc = true;
        for(int i = 0; i<3; i++){ // 상, 좌, 좌상 확인
            int nexty = y + delta[i][0];
            int nextx = x + delta[i][1];

            if(0 <= nexty && nexty < height && 0<= nextx && nextx < width && dp[nexty][nextx] != 0){
                res = Math.min(res, dp[nexty][nextx]);
            }else{ // 정사각형 못만드는 경우
                suc = false;
                break;
            }
        }

        if(!suc) res = 0;

        return res;
    }
}