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

오늘의 과제

리트코드 Medeum으로 분류된 Count Square Submatrices with All Ones입니다.

 

문제의 유형은 어제에 이어 DP(Dynamic Programing)입니다.

문제

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

 

 

먼저 문제 요구사항 요약입니다.

 

1과 0으로 구성된 행렬이 주어질 때 모두 1로 구성된 정사각형 부분 행렬의 수를 반환하면 됩니다.

 

문제의 예시 2번을 보면 다음과 같이 정사각형의 개수를 구하면 됩니다.

(1*1 = 6, 2*2 = 1)

 

1 * 1의 경우는 쉽게 구할 수 있으니 2 * 2 크기의 정사각형을 구하는 방법부터 찾아봅니다.

 

사각형의 크기는 알 수 없으나 커지면 커질수록 오른쪽 대각선 아래로 커지는 형태를 띄게 됩니다.

생각하기 나름이긴 한데...

 

그래서 확장성을 고려하여 오른쪽 대각선에서부터 1로 이루어진 정사각형 여부를 확인합니다.

 

즉, 첫 번째 행과 첫 번째 열은 주어진 행렬을 그대로 사용하고

실제 확인은 1,1 좌표부터 이루어집니다.

 

확인을 할 때에는 자기 자신이 1이 아니라면 어차피 정사각형은 만들 수 없으니 넘어가고,

1인 경우에 왼쪽, 왼쪽 위, 위의 값 중 최소값에 자기 자신을 더한 값을 넣어줍니다.

 

그러면 모두 1일 경우엔 세 값중 최소값이 1이 나오고, 자기 자신의 위치인 1*1 크기인 1을 더하면 2가 되겠죠?

(왼) dp[1][1]의 경우 = 위 값에 0이 있으니 자기 자신의 값인 1만 기억 (오) dp[2][2]의 경우 = 모두 1이니 자기 자신 + 1인 2를 기억

 

이를 점화식으로 만든다면 다음과 같이 만들 수 있습니다.

dp[i][j] = min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]) + 1

 

 

 

 

코드입니다.

class Solution {
    public int countSquares(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int answer = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 현재 값이 1이 아니면 구하지 않는다.
                if (matrix[i][j] != 1) continue;
                // 첫 행과 첫 열은 1 * 1 외에 정사각형을 구할 필요가 없다.
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
                answer += dp[i][j];
            }
        }

        return answer;
    }
}

 

 

 

배운 점

처음 요구사항부터 이해가 안돼 조금 당황했습니다.

 

사실 이렇게 직관적일때가 편하고 현실 세계의 문제에 빗대어 나오기 시작하면

더 어려워질게 뻔한데 벌써 막히니 자신감이 조금 떨어지네요.

 

DP라는 문제 유형이 난이도가 있단는 것을 아는지 항해99 측에서 조금 집중적으로 연습시키는 것 같습니다.

 

연습말고 빠른 길은 없습니다.

 

오늘도 포기하지 않겠습니다.

 

 

오늘의 한줄평

연애 말고도 10번찍어(풀어) 안넘어가는 나무(문제) 없다