Lv2. 가장 큰 정사각형 찾기

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

예를 들어

가 있다면 가장 큰 정사각형은

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

---

입출력 예

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

 

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

프로그래머스

---

 

처음엔 테이블의 dfs 방식으로 각 칸을 조회하는 방식으로 하였으나, 당연히 효율성에서 통과하지 못하였고 정확성도 몇가지가 통과하지 못하였다. 그래서 과감히 포기하고 DP 방식으로 진행하였다.

그리고 DP를 진행하려면 규칙을 찾아내야 한다.

아래와 같은 과정을 거쳐 찾아내보도록 한다.

 

기본적으로 1이 적힌 한칸은 크기 1인 정사각형이다.

1

 

그리고 크기가 4인 (2x2) 정사각형이 가능하려면 아래와 같은 형태여야한다.

1	1
1	1

 

만약 위에 테이블 중 한칸이라도 0이라면 크기가 2인 정사각형이 불가능해진다.

그리고 크기가 9인 정사각형이 가능하려면 아래와 같은 형태여야 한다.

1	1	1
1	1	1
1	1	1

위와 같은 크기가 9인 정사각형이 가능하려면 9칸 모두 1이 존재하여야 한다.

그리고 가만히 보면 아래와 같이 각 색깔칸들이 크기가 4인 정사각형이야만 전체 9인 정사각형이 만들어진다.

 

이러한 규칙은 크기가 16인 (4X4) 정사각형 그리고 더 큰 정사각형들 또한 마찬가지이다.

그렇다면 정사각형이 만들어진 테이블 기준으로 우측하단 칸에 현재 만들어진 정사각형의 한변 크기를 저장해두기로 하자. 그렇다면 위에 테이블의 회색 바탕의 칸에서 현재 3X3의 정사각형이 만들어졌는지 확인이 가능하기 때문이다.

 

바로 아래와 같이 말이다.

1	1	1
1	2	2
1	2	3

 

근데, 진행 과정 중에 의문이 들것이다.

위에 테이블에서 색깔이 칠해진 칸은 2로 체크했다고 치고

for문을 이용하여 좌표 이동하여 화살표 방향대로 우측칸으로 이동했다고 생각해보자

좌측은 2, 상단은 1, 좌상단칸은 1이다.

현재 기준 좐표칸에 뭐라고 기록해야 할까?

눈으로 보게 되면 그냥 2라는것을 알 수있다.

2행 3열까지 모두 1인 칸이기 때문이다.

그렇지만 어떠한 규칙으로 해당칸에 2를 체크해야할까?

바로 좌측, 상단, 좌상단 칸들 중에 가장 작은 값 + 1을 하여 현재칸에 기록하면 된다.

 

DP 방식으로 풀기 위한 큰 규칙의 발견 과정을 나만의 식대로 이렇게 정리해 보았다.

아래는 해당 방법으로 해결한 코드이다.

 

---

import java.util.*;
class Solution
{
    public int solution(int [][]board)
    {      
        int result = 1;
        boolean isInLogic = false;
        for(int i = 1; i < board.length; i++){
            for(int j = 1; j < board[i].length; j++){
                if(board[i][j] == 0) continue;
                if(j >= board[i-1].length) continue; //현재 행의 열 인덱스 보다 이전 행의 길이가 짧을 경우 
                isInLogic = true;
                board[i][j] = Math.min(Math.min(board[i][j-1], board[i-1][j]) , board[i-1][j-1]) + 1;
                if(board[i][j] > result) result = board[i][j];
            }
        }
        if(!isInLogic){ //행의 길이가 2보다 작을 경우 위에 로직 자체를 들어가지 않기 때문에, 그렇다고 최초 result 값을 0으로 하였다간 반례가 생긴다.
            result = 0;
            for(int i = 0; i < board.length; i++){
                for(int j = 0; j < board[i].length; j++){
                    if(result < board[i][j]) {
                        result = board[i][j];
                        break;
                    }
                }
            }
        }
        return result * result;
    }
}

 

---

반례

• [[1]] : 1
• [[0]] : 0
• [[1, 0], [1, 0]] : 1
• [[1, 1, 1, 1], [1, 1, 1, 1]] : 4
• [[1, 1], [1, 1, 1, 1]] : 4
• [[1, 0, 0], [0, 1, 1], [0, 1, 1]] : 4
• [[0, 0, 0], [0, 1, 0], [0, 0, 0]] : 1
• [[1, 1, 1], [1, 0, 1], [1, 1, 1]] : 1
• [[0, 0, 0], [0, 1, 1], [0, 0, 0]] : 1
• [[0, 0], [0, 1]] : 1
• [[1, 0, 0, 0, 0, 0, 0]] : 1
• [[0, 1, 1, 1, 1, 1, 0], [0, 0, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 1, 0]] : 9
• [[0], [1], [1, 1]] : 1
• [[0, 0, 0, 0]] : 0
• [[1, 1, 1, 1], [0, 1, 1, 1], [0, 1, 1, 1]] : 9
• [[1], [1, 1], [1, 1, 1]] : 4
• [[1, 1, 1], [1], [1, 1, 1]] : 1
• [[1, 1, 1], [1, 1], [1, 1, 1]] : 4
• [[1], [1, 1, 1, 1], [1, 1]] : 4