Problem
https://leetcode.com/problems/count-square-submatrices-with-all-ones/
Sol
0과 1로 만들어진 행렬(matrix)에서 1로 만들 수 있는 정사각형의 최대 개수를 구하는 문제
Dynamic Programming
어떤 단계에 있을 때 처음부터 여기에 어떻게 왔는지는 중요하지 않다.
바로 그 앞 단계에서 어떻게 여기까지 왔는지 중요
특정 위치 i에 도착해있다고 가정하고 '그럼 그 전에도 어떻게든 알아서 잘 왔겠지' 라는 생각으로 푸는 형식입니다.
🌱 참고
Dynamic Programming lectures
Dynamic Programming lectures
www.youtube.com
문제는 짧은데 생각해내는데 너무 오래걸려서 냅다 유튜브로 DP 시청해버렸습니다. 머리아파요
해결 방법
👀 현재 위치가 1이라면, 현재 위치의 주변(왼쪽, 위쪽, 왼쪽 위 대각선)에 만들 수 있는 정사각형이 있나 살핍니다. (니가 하면 나도 한다는 마인드)
오늘 문제는 그림을 그려서 완벽하게 이해하고 넘어가야 다음에 DP 문제를 풀때도 좋을 것 같아서 그림으로 그려보았습니다. 제가 이해하기 쉽게 그린 것이라 오류가 있다면 알려주세요.. matrix의 값이 1일 경우 주변을 살피고 dp에 값을 업데이트 하는 것을 반복합니다. Input은 다음과 같습니다.
Input: matrix =
[
[0,1,1,0],
[1,1,1,1],
[0,0,1,0]
]
DP 준비 과정
1. matrix의 row, col 의 수 구하기
2. dp[rows][cols] : 주어진 matrix와 같은 크기의 행렬 0으로 초기화
⭐ 현재 위치 matrix[i][j]에서 왼쪽, 위쪽, 왼쪽 위 대각선을 보았을 때 만들 수 있는 정사각형의 개수를 저장하는 용도
matrix[i][j]의 값이 1일 경우 dp에 count
3. 첫번째 행 혹은 열일 경우 왼쪽과 위쪽이 없으므로 dp[i][j] = 1
4. 그렇지 않은 경우, 왼쪽 위쪽 왼쪽 위 대각선의 최솟값에 +1
현재 위치는 (i,j) 입니다. matrix에서 주변 친구가 0이라면 정사각형을 만들 수 없습니다. dp에서도 주변의 최솟값이 0이기 때문에 최솟값+1 해도 원래 값 그대로 1밖에 하지 못합니다. 하지만 주변 친구가 모두 작은 정사각형이라면 나는 더 큰 정사각형이 될 수 있습니다 .
반복 · · ·
5. 위의 과정을 반복해 저장된 dp[rows][cols]의 값을 모두 더해주면, 최대로 만들 수 있는 정사각형 개수를 구할 수 있습니다.
✔ Answer
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
# 1로 정사각형 만들 수 있는 최대 개수 구하기
# side 1 인거부터 주위에 만들 수 있는 정사각형있나 살피기(왼, 위, 왼대각) : dp에 개수 저장
rows, cols = len(matrix), len(matrix[0])
# 각 셀에서 끝나는 정사각형 부분 행렬의 최대 크기를 저장
# dp = [[0]*cols for _ in range(rows)]
dp = []
for _ in range(rows):
row = [0] * cols
dp.append(row)
max_squares = 0
for i in range(rows):
for j in range(cols):
if matrix[i][j] == 1:
# 첫번째 행 or 첫번째 열
if i == 0 or j == 0:
dp[i][j] = 1
# 왼쪽, 위쪽, 왼쪽 위 대각선 최소값에 + 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_squares += dp[i][j]
return max_squares
💬 소감
니가 하면 나도 한다! 니가 안하면 나도 안함