[프로그래머스] 가장 큰 정사각형 찾기

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> board)
{
    int answer = 0;
    int row = board.size();
    int column = board[0].size();
    
    vector<vector<int>> length(row, vector<int>(column, 0));

    for(int i=0; i<row; i++){
        length[i][0] = board[i][0];
        answer = max(answer, length[i][0]);
    }
    
    for(int j=0; j<column; j++){
        length[0][j] = board[0][j];
        answer = max(answer, length[0][j]);
    }
    
    for(int r=1; r<row; r++){
        for(int c=1; c<column; c++){
            if(board[r][c] == 1){
                length[r][c] = min({length[r-1][c], length[r][c-1], length[r-1][c-1]}) + 1;
                answer = max(answer, length[r][c]);
            }
        }
    }

    return answer * answer;
}

---

📝 풀이

이 문제는 각 위치의 점을 정사각형의 오른쪽 아래 꼭짓점이라고 생각하여 계산하는 방법으로 풀었습니다.

 

1) 각 위치의 점을 정사각형의 오른쪽 아래 꼭짓점이라고 하기 위해서는 첫 번째 행과 열은 그대로 사용합니다.

2) 두 번째 행과 열부터 계산을 시작합니다.

3) 기준점이 1이라면 왼쪽, 왼쪽 위 대각선, 위에 있는 점들 중 최솟값과 1을 더하여 갱신합니다.

정사각형이 되려면 세 점들이 모두 1이상이어야 하기때문에 최솟값이 0이라면 정사각형이 될 수 없습니다.

 

그 다음 점을 살펴보면 최솟값이 1이기 때문에 1+1=2로 갱신됩니다.

길이가 2인 정사각형인 모습을 확인할 수 있습니다.

length 값이 갱신될 때마다 answer과 비교후 answer을 큰 값으로 갱신합니다.

이 과정을 마지막 행과 열까지 쭉 반복합니다.

 

최종적으로 정사각형의 넓이를 반환해야 하기때문에 answer * answer 을 return 합니다.