Programmers [가장 큰 정사각형 찾기]

Programmers [가장 큰 정사각형 찾기]

---

   Problem   

코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 가장 큰 정사각형 찾기

---

   Code   

#include<vector>
 
using namespace std;
 
int solution(vector<vector<int>> board)
{
    int width = board[0].size();
    int height = board.size();
 
    int answer = 0;
 
    for (int i = 0; i < width; i++) if (board[0][i]) answer = 1;
    for (int i = 0; i < height; i++) if (board[i][0]) answer = 1;
 
    for (int i = 1; i < height; i++) {
        for (int j = 1; j < width; j++) {
            if (board[i][j]) {
                board[i][j] += min(board[i - 1][j], min(board[i - 1][j - 1], board[i][j - 1]));
 
                answer = max(answer, board[i][j]);
            }
        }
    }
 
    return answer * answer;
}

---

   How to solve   

  Dynamic programming 을 이용한 문제. 15 ~ 23번째 line 에서 본격적인 DP가 진행이 된다. board[i][j] 는 이전의 값을 참고하기 위해 i, j 가 0이 아닌 1부터 시작한다.

Before DP

  위 사진의 파란색 화살표 순서로 (위에서 아래로) DP 가 진행이 된다. 18번째 line이 핵심이 되는데, 18번째 line에선 현재 board[i][j]의 값에 board[i - 1][j], board[i - 1][j - 1], board[i][j - 1] 의 값중 가장 작은 값을 더하게 된다.

더해지는 원리

  board[i][j]에 이와 같은 과정을 걸치면 위 <Before DP> 사진은 아래와 같이 될 것이다.

After DP

  빨간 테두리가 정답이 될 것이고 그 빨간 정사각형의 한 변의 길이는 그 정사각형 오른쪽 아래에 있는 4가 될 것이다. 문제에서 요구하는 return값은 넓이이므로 이 값을 제곱한 값을 return 해주면 될 것이다.

  

  12, 13번째 line 은 혹시 위 <Bafore DP> 사진의 주황색 영역 (DP를 직접적으로 진행하지 않는 영역) 에 1이 있으면 answer 를 1로 변경하는 코드이다. 이 부분은 당연하게 꼭 필요하다. 아래와 같은 case도 있기 때문이다.

  이 경우에는 DP를 진행하는 과정에선 answer 의 값은 계속해서 0일 것이다. 하지만 12, 13번째 line 에서 answer 의 값이 1인것을 알게될 수 있다.