[완전탐색/자바] 코드트리 IL.양수 직사각형의 최대 크기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 해석

위 문제는 N x M 크기의 배열 안에서 구성될 수 있는 직사각형을 모두 탐색하여, 그 직사각형이 모두 양수로 이루어진 케이스 중 최대의 넓이를 출력하는 문제이다.

 

n과 m이 20 이하의 자연수이므로, 그 내부 직사각형의 길이를 for loop으로 정의하고, 기준 좌표를 정의하고, 넓이 내의 좌표를 모두 for loop으로 순회하더라도 어림잡아봐야 O(n^3 * m^3)인데, 이렇게 해봐야 최악의 경우 64,000,000번의 연산을 하게 되고, 실제로는 이보다 더 작을 것이므로 완전탐색으로 수행해도 충분히 해결가능한 문제이다.

 

문제 풀이

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

public class Main {
    private static int n, m;
    private static int[][] arr;
    private static Queue<Integer> pq = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 높이가 n'인 직사각형
        for (int i = 1; i <= n; i++) {
            // 길이가 m'인 직사각형
            for (int j = 1; j <= m; j++) {
                // 기준 y좌표
                for (int y = 0; y < n; y++) {
                    // 기준 x좌표
                    for (int x = 0; x < m; x++) {
                        boolean isRectangle = true;
                        // 기준으로부터 정의 높이만큼 y좌표 순회
                        for (int k = y; k < y + i; k++) {
                            // 기준으로부터 정의 길이만큼 x좌표 순회
                            for (int l = x; l < x + j; l++) {
                            	// 범위에 맞지 않으면 pass
                                if (!inRange(k, l)) {
                                    isRectangle = false;
                                // 만약 하나라도 음수인 요소가 있다면 pass
                                } else if (arr[k][l] <= 0) {
                                    isRectangle = false;
                                }
                            }
                        }
                        if (isRectangle) {
                            pq.add(-(i * j));
                        }
                    }
                }
            }
        }
        if (pq.isEmpty()) {
            System.out.println(-1);
        } else {
            System.out.println(-pq.poll());
        }

    }

    private static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < m;
    }
}