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

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

문제 설명

• 0과 1로 이루어진 직사각형(행렬) vector<vector<int>> board가 주어질 때
  1로만 이루어진 정사각형의 넓이를 return하는 문제이다.

• 정사각형의 변은 x축,y축에 평행하다는 조건이 있으므로 마름모 형태의 정사각형은 배제한다.

• 행렬의 크기가 각각 1000이하의 자연수 이므로 총 1,000,000의 크기를 갖는 행렬이다. 따라서 O(n^2)의 시간이 걸리면 효율성을 통과 못 할 것으로 생각한다.

접근 방법

• 행렬을 처음부터 끝까지 한번만 읽으면 최대 정사각형이 나올 수 있다 생각했다.
  따라서 O(n)시간에 풀 수 있다.

• board[x][y] != 0 일때 board[x][y]지점에서 위, 왼쪽, 왼쪽대각선 (즉,[x-1][y],[x][y-1],[x-1][y-1])의 저장된 수를 기반으로 [x][y]지점에서 정사각형의 크기가 얼마가 되는지 알 수 있다.

• [x][y]가 추가되어 정사각형이 되려면 [x-1][y],[x][y-1],[x-1][y-1]중 최소값+1 정사각형의 한변 길이가 된다.

• 이를 for문으로 탐색하면 board에는 최종적으로 각 지점에서 정사각형의 한변 길이가 저장된다.

• 이를 코드로 옮겨보자면

풀이1

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

int solution(vector<vector<int>> board)
{
    int answer = 0;
    bool f = false;
    int ans = 0;
    
    for(int i=1;i<board.size();i++){
        for(int k=1;k<board[i].size();k++){
            if(board[i][k]!=0){
                // 해당 지점을 추가했을 때 정사각형 한변의 크기 구하기
                board[i][k] = 1+min(board[i-1][k],min(board[i][k-1],board[i-1][k-1]));
                // 최대값일 경우 저장
                if(ans<board[i][k]) ans = board[i][k];
            }
        }
    }
    answer = ans*ans;   
    return answer;
}

결과1

• 실패... 그것도 테스트케이스 1번에서... 따라서 사소한 실수 같아 생각해보았다.
• for문이 모두 1부터 시작하니까 여기서 문제가 있을것으로 판단하였고, 행이나 열의 크기가 1이어서 1인덱스가 없을때를 생각하였다.
• 이에 코드를 수정하였다.

풀이2

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

int solution(vector<vector<int>> board)
{
    int answer = 0;
    bool f = false;
    int ans = 0;
    if(board.size()==1||board[0].size()==1){
        return 1;
    }
    for(int i=1;i<board.size();i++){
        for(int k=1;k<board[i].size();k++){
            if(board[i][k]!=0){
                board[i][k] = 1+min(board[i-1][k],min(board[i][k-1],board[i-1][k-1]));
                if(ans<board[i][k]) ans = board[i][k];
            }
        }
    }
    answer = ans*ans;   
    return answer;
}

결과2

후기

• 사실 풀이2에서 if문을 추가하는 대신 int ans=1로 초기화 하면 정답이긴 하지만 가독성과 이해를 위해 if문을 추가했다. :)