[코드 트리] 양수 직사각형의 최대 크기 (JAVA)

[코드 트리] 양수 직사각형의 최대 크기 (JAVA)

🗒️알고리즘 분류

#완전 탐색 #brute force

📌기억해야 할 포인트

모든 종류의 직사각형을 어떤 방식으로 만들지 알면 쉬운 문제이다.

• 이전에 풀었던 겹쳐지지 않는 두 직사각형 문제에서 처럼 임의의 한 점(i,j) 를 기준으로 (i+x, j+y)를 하면 직사각형의 양 꼭지점이 나오므로 쉽게 직사각형을 구할 수 있다.

📍실수할 만한 포인트

• 이 문제에선 배열의 입력 값들이 모두 음수인 경우에 -1 을 반환해야 한다는 것을 잊지 말자.
  • 이 문제에선 간단하게 boolean flag 변수로 제어를 해주었다.
  • 더 간단하게는 처음부터 answer 를 선언할 때 -1 로 해주면 된다.

📝풀이 코드(JAVA)

import java.util.*;

public class Main {
    private static int N = 0;
    private static int M = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] arr = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        sc.close();

        N = n;
        M = m;
        int answer = 0;
        boolean flag = false;

        for (int x = 0; x < n; ++x) {
            for (int y = 0; y < m; ++y) {
                for (int x2 = x; x2 < n; ++x2) {
                    for (int y2 = y; y2 < m; ++y2) {
                        if (isAllPlus(arr, x,y,x2,y2)) {
                            answer = Math.max(answer, getArea(x,y,x2,y2));
                            flag = true;
                        }
                    }
                }
            }
        }   

        if (flag) {
            System.out.println(answer);
        } else {
            System.out.println(-1);
        }
        return;
    }

    private static boolean isAllPlus(int[][] arr, int x, int y, int x2, int y2) {
        for (int i = x; i <= x2; ++i) {
            for (int j = y; j <= y2; ++j) {
                if (arr[i][j] <= 0) {
                    return false;
                }
            }
        }

        return true;
    }

    private static int getArea(int x, int y, int x2, int y2) {
        return (Math.abs(x-x2)+1) * (Math.abs(y-y2)+1);
    }
}

⏰총 풀이시간

• 25분