99클럽 코테 스터디 21일차 TIL Count Square Submatrices with All Ones

https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/

 

 

1. 문제 및 접근

 

 

0 or 1의 수가 주어지고 arr[][]가 주어지면

정사각형의 갯수 return

매트릭스 안에서 모든 수 더하기 느낌으로 하다 1,4,9가 만들어질 때 카운팅 +1 해주는 방식으로 가자

 

ex) {1,1}

       {1,1}  일 때 (1,1) 4를 저장하는 건 되는데  +1의 규칙성을 어떻게 정하지 ?

 

 

dp[i][j] = matrix[i][j] + dp[i - 1][j] + dp[i][j] - dp[i - 1][i - 1] 까진 느낌 오는데

여기서 4개 9개가 1이 다 채워져 있다면 +1씩 계속 해줘야 하는데 이것도 다시 검사  ? 너무 시간 낭비인데..

 

 

 

 

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

 

 

 

 

 

2. 풀이

package 알고리즘.프로그래머스.항해99.삼주차;

public class countSquareSubmatriceswithAllOnes {

    // 0 or 1의 수가 주어지고 arr[][]안ㅇ 주어지면
    //정사각형의 갯수 return
    // 매트릭스 안에서 모든 수 더하기 느낌으로 하다 1,4,9가 만들어질 때 카운팅 +1 해주는 방식으로 가자
    // 11
    // 11 일 때 (1,1) 4를 저장하는 건 되는데  +1의 규칙성을 어떻게 정하지 ?
    // dp[i][j] = matrix[i][j] + dp[i - 1][j] + dp[i][j] - dp[i - 1][i - 1] 까진 느낌 오는데
    // 여기서 4개 9개가 1이 다 채워져 있다면 +1씩 계속 해줘야 하는데 이것도 다시 검사 ?

    private static int[][] dp;
    public static void main(String[] args) {

        int[][] arr = new int[][]{{1, 1}, {1, 1}};

        countSquareSubmatriceswithAllOnes main = new countSquareSubmatriceswithAllOnes();
        
        System.out.println(main.countSquares(arr));



    }

    public int countSquares(int[][] matrix) {

        int answer = 0;

        dp = new int[matrix.length][matrix[0].length]; // 같은 배열 크기로 초기화


        for (int i = 0; i <matrix.length; i++) {

            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 1) { // 현재 수가 1인데, 가장자리의 수를 기본 값으로 계속 세팅
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;

                    } else {

                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }

                    answer = answer + dp[i][j];


                }

            }
        }


        return answer;

    }

}

 

 

전체 풀이

 

 

 

2-1.  내 해석

 

 

 

사실 Hint를 보고 예전에 비슷하게 2차원 배열의 전체 합을 구하고, 원하는 index들이 들어오면 그 부분만 짤라서

 

계산하는 문제를 풀어봐서 

 

dp[matrix.length][matrix[0].length]의 값을 구하는 방법 을 적용해봤다.

 

 

 

 

직전에 저장된 값들([i][j-1] ,[i-1][j])을 더하고 중복 부분을 빼주고,  현재 들어온 배열의 값을 더해주는 누적합 dp를

떠올렸는데 여기서 문제는 수의 덧셈이 아닌 정사각형의 갯수이다.

 

 

1을 정사각형으로 더하는 건 쉬웠는데 ,

 

ex) {1,1}

      {1,1}

 

 의 경우 4가 아닌 5가 되게 하는 과정에서 막혔다 조금 더 생각하면 나올 거 같은 느낌이지만 내가 정해놓은

dp 마지노선 1시간이 넘어서 답을 보고 풀어버림 ㅠㅠ

 

 

 

 

 

2-2.풀이

 

 

 

먼저 현재 matrix[i][j] 값이 1일때만 작동하게 한다. 0이면 볼 필요도 없으니

 

 

 

누적합을 dp 자체에 구하는 것이 아니라 answer에 현재 구한 값들을 다 더해줌

 

현재 배열에 들어온 수가 1이라면,

 

전부 0으로 초기화 되어 있는 dp 배열의 가장자리를 1로 다 넣어준다.

 

 

 

matrix[][] 가 전부 1로 들어왔다고 가정하면

 

1  1  1
0 0 0
0 0 0

 

 

이런 식으로 dp 배열이 채워지는 것이다.

 

 

 

 

2-3. 실제 갯수 세기

 

 

 

배열 끝이 아니라면 ?

 

이제 로직이 동작할 차례인데,

 

 

 

dp[i][j]가 (i, j) 위치에서 끝나는 가장 큰 정사각형인데, 

 

그렇다면 이 크기는 위, 왼쪽, 대각 왼쪽 위의 크기에 영향을 받을 것이다.

 

 

dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 의 세개의 경우 중 가장 작은 경우에 +1을 해주면

 

 

                                         {1, 1}

그 1 들이 다 채워져 있다면 {1, 1}   min 값은 (1,1,1)에   포함된 큰 정사각형을 +1이 되어, 2가 될 것이고,

 

 

 

아니라면 가장 작은 값에 1의 원래 수를 더해 현재 [i][j]를 채워나가게 될 것이다.

 

 

 

 

 

그렇게 구한 현재 dp[i][j]의 값을 answer에 누적하면 끝

 

 

 

 

 

번외. [2][2] 의 값은 ?

 

 

dp[][] 배열

1	1	1
1	2	2
1	2	3

 

 

 

이것도 마찬가지로 큰 정사각형을 구하려면, min(2,2,2)값  중 +1을 하면  3이 된다~

 

 

 

 

 

 

성공이다..

 

 

 

 

 

3. 마무리

 

 

 

 

아니... 내 한계가 너무 명확하다 계속 도전하지만, 어떻게 이걸 바로 떠올릴 수 있을까 ?

 

전에 좀 풀어봐서 2차원 배열에 관한 점화식 자체는 떠올려도 누적합을 구하기 위한 것이였다면 응용이 충분히 가능해야 할텐데..

 

응용을 못하니까 너무 화가 나네 ㅠㅠㅠ

 

분명히 4개의 1이 있다면 +1할 수 있는 과정을 내가 구한 누적합에서도 찾을만 할 것 같은데..

 

 

제일 무서운 게 틀린 답일수도 있는데 자체가 애매하니 못 놓고 붙잡는 시간이 길어진다

 

 

 

그래서 dp 문제일 경우 더 제한 시간을 두고, 푸는 걸 잊지말자..

 

 

(어릴 때 서당 다녔는데 훈장님이 배부르기 한숟갈 전에 그만두랬어.. 내 인생을 관통하는 명언이시다..)