[코드트리] 양수 직사각형의 최대 크기 Java 풀이

 

문제 요약

격자 내에서 모든 값이 양수로만 이루어진 직사각형 중 최대 크기를 구하는 문제입니다.

그런 직사각형이 없다면 -1 을 출력합니다.

 

문제 해결 프로세스

이 문제는 완전 탐색으로 풀어야 합니다.

어느 칸에 어떤 숫자가 들어있을 지 모르기 때문이죠.

그렇다면 어떻게 완전탐색을 할 수 있을까요?

 

저는 직사각형의 시작점 (i, j)을 정하고, 끝점(k, l)을 정해서 풀었습니다.

 

직사각형 꼭짓점의 행, 열의 좌표가 될 수 있는 범위를 나타내면 다음과 같습니다.

(0 ~ n-1 으로 놓고 풀었지만 편의상 아래와 같이 표시할게요.)

 

시작점 

i : 1 ~ n 

j : 1 ~ m

 

끝점

k : i ~ n   (끝점의 행이 시작점의 행보다는 크거나 같아야 합니다.)

l : j ~ m   (끝점의 열이 시작점의 열보다는 크거나 같아야 합니다.)

 

 

이렇게 놓았다면 이제 무려 4중 for문을 돌리면 되겠습니다.

        // 시작점 정하기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 끝점 정하기
                for (int k = i; k < n; k++) {
                    for (int l = j; l < m; l++) {
                        // getSize에 시작점, 끝점을 인자로 주며 호출해
                        // 각 위치에서 만들어질 수 있는 직사각형의 size 구한 후,
                        // maxSize보다 크다면 최대 크기 갱신
                        maxSize = Math.max(maxSize, getSize(i, j, k, l));
                    }
                }
            }
        }

 

getSize 함수의 코드는 다음과 같습니다.

주석으로 과정을 상세히 설명해두었습니다.

    private static int getSize(int i, int j, int k, int l) {
        int size = 0; // 현재 만들어지는 직사각형의 크기
        
        // 시작점과 끝점이 정해졌으니 
        for (int r = i; r <= k; r++) { // r은 시작점 i부터 끝점 k까지
            for (int c = j; c <= l; c++) { // c도 시작점 j부터 끝점 c까지
                // 그중 하나라도 0이나 음수가 있다면
                if (arr[r][c] <= 0) return -1; // -1 return
                size ++; // 아니라면 일단 size 하나씩 증가
            }
        }
        // 여기까지 왔다면 음수가 없었다는 것
        return size; // size 값 return
    }

 

여기에서 주의할 점은 0이나 음수를 만났을 때 0이 아닌 -1 을 리턴해주어야 합니다.

만약 양수 직사각형을 찾을 수 없다면 -1을 출력해야 하는데, 여기서 0을 리턴하게 되면 정답값이 0으로 업데이트되어 버리기 때문입니다.

저도 습관적으로 0을 리턴하다가 이부분을 한 번 실수했네요 ㅋㅋㅋ

 

궁금한 점이나 더 좋은 풀이가 있다면 댓글로 언제든지 피드백 남겨주세요! :) 🦊