[C++로 풀이] 가장 큰 정사각형 찾기 (DP)⭐⭐

📌 가장 큰 정사각형 찾기

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include<vector>
#include<algorithm>
using namespace std;

int solution(vector<vector<int>> board)
{
    int answer = 1;
    int max = 0;
    vector<vector<int>> dp(board.size(), vector<int>(board[0].size()));
    
    for(int i = 0; i < board.size(); i++){
        for(int j = 0; j < board[i].size(); j++){
            if (i == 0 || j == 0 || board[i][j] == 0) 
                dp[i][j] = board[i][j];
            else
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            
            if (max < dp[i][j]) 
                max = dp[i][j];
        }
    }
    
    answer = max * max;
    return answer;
}

dp[i][j]는 board[i][j]를 “우하단”으로 하는 최대 크기의 정사각형의 길이가 된다.

뭔가 말로 설명하기가 어렵다.. 위와 같은 식으로 영향을 받기 때문에 이런 점화식이 만들어진다고 보면 될 것 같다. 다이나믹 프로그래밍이라 위쪽에서 아래쪽으로(행). 왼쪽에서 오른쪽으로(열) 진행되기 때문에 해당 원소가 정사각형이 될 수 있는지는 사실상 dp[i-1][j-1], dp[i][j-1], dp[i-1][j] 이렇게 3 개를 살펴보면 된다.

점화식 👉 dp[i][j] = Min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1

• 이웃한 3개 영역 중 가장 최소 값에다가 1 을 더하면 된다.
  • 아래의 ? 자리에 들어갈 수는 2 가 된다. ( = 1 + 1)

    2 1
    2 ? 
    

  • 아래의 ? 자리에 들어갈 수는 1 이 된다. ( = 0 + 1)

    0 1
    1 ? 
    

• 첫 행이거나 첫 열이거나 board[i][j] 값이 0 이면 dp[i][j] = board[i][j]
  • 첫 행과 첫 열은 3 개 중 작은 값을 뽑을 수가 없으며 최대로 만들 수 있는 정사각형 길이가 1 밖에 되지 않는다. 따라서 그냥 자기 자신의 값으로 대입한다.
  • board[i][j] 값이 0 일땐 정사각형이 될 수 없으므로 그냥 0 으로 대입.
• 알고리즘 헤더의 min 함수가 인수를 2 개만 받기 때문에 코드에선 min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) 라고 나눠서 구현했다.

0 1 1 1
1 1 2 2
1 2 2 3
0 0 1 0

최종적으로 문제에서 준 예제로는 dp 배열은 위와 같은 모습이 될 것이다. 3이 제일 최대값이기 때문에 넓이를 구하는 답은 \(3^2 = 9\)가 된다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기