[프로그래머스] 가장 큰 정사각형 / python3, C++ / level2

✏️ 문제 링크

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

 

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

 

 

---

✏️ 문제 설명 (더보기 클릭 👆🏻)

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

---

입출력 예

boardanswer

[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

 

---

하..정말 디피는 왜 해도해도 어려운걸까~~ 

우선 DP라고하면.. 보통 값을 차곡차곡 쌓아 결과물을 도출해 낼 수 있는 경우의 문제들을 다룬다. 

위 문제는 이러한 사고를 찾아내기까지 어려움이 있는 듯 싶다. 

한번 차분히 정리해보자 🔮

 

✏️ DP로 풀어야 하는 이유

우선 해당 문제를 DP로 해결해야 하는 이유이다.

• DP로 해결하지 않는 경우 삼중 포문을 실행해야한다. 
  
  • 삼중 포문은 (정사각형을 도는것 2중포문 + 가능한 정사각형의 크기를 확인하는 것에 1중 or 2중)
  • 삼중 포문 진행시 1,000,000,000의 연산 수가 나온다. (효율성 fail, 제한시간 fail)

 

 

위의 사고 다음에는 '오 그럼 포문으로는 가능성이 없으니 다른 방식을 생각해보아야겠다!' 가 나올테고...

그 다른 방식은 바로 DP이다 ㅎㅅㅎ

 

DP를 사용하기 위해서는 밑의 프로세스를 탄다. 

 

💡 규칙을 찾고,  식을 세워서 , 풀어! 💡

 

위의 흐름대로 문제를 풀어보쟈 

 

✏️ 문제 풀이

아래와 같은 board가 있다! 

 

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

1, 1부터 보았을 때 오른쪽 아래를 기준으로 위, 대각선위, 왼쪽 중 가장 작은 값 + 1을 해준 값이 해당 칸의 값으로 된다! ㅠㅜ

DP는 너무 어렵다..설명도 어렵고~ 푸는것도 어렵고~ 다 어렵고~ 

 

✏️ 문제 코드 (python3)

def solution(board):
    answer = 0
    n=len(board)
    m = len(board[0])
    if n==1 and m==1:
        if board[0][0] == 1:
            return 1
        else: 
            return 0
        

    for i in range(1, len(board)):
        for j in range(1, len(board[i])):
            if board[i][j]:
                board[i][j]=min(board[i-1][j], board[i][j-1], board[i-1][j-1])+1
                answer = max(answer, board[i][j] ** 2)
                

    return answer

 

 

✏️ 문제 코드 (C++)

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

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