알고리즘(C++) / 프로그래머스 level 2 : 가장 큰 정사각형 찾기

level 2 : 가장 큰 정사각형 찾기

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

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

 

코드

//프로그래머스 가장 큰 정사각형 찾기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> board)
{
    int answer = board[0][0];
    
    for (int i = 1; i < board.size(); i++) {
        for (int j = 1; j < board[0].size(); j++) {
            if (board[i][j] == 1) {
                board[i][j] = min({ board[i - 1][j - 1], board[i - 1][j], board[i][j - 1] }) + 1; //왼쪽위 대각선, 왼쪽, 위 방향중 가장 작은 값
                answer = max(answer, board[i][j]); //배열 중 가장 큰 값
            }
        }
    }

    return answer * answer; //정사각형 사이즈
}
int main() {
    vector<vector<int>> board = { {0,1,1,1}, {1,1,1,1},{1,1,1,1}, {0,0,1,0} };
    cout << solution(board) << "\n";
    return 0;
}

 

고찰

문제풀이 방법을 한번에 생각하지 못하고 DFS, BFS로 풀어야되나 생각했지만 비교적 간단하게 문제풀이를 하였다.

여러개의 요소 중 가장 최솟값을 찾기 위해서 algorithm헤더의 min함수를 사용한다. 배열처럼 여러개의 요소를 { } 안에 넣어주면 여러개의 값중 가장 최솟값을 찾을 수 있다. 최댓값도 마찬가지이다.

board[i][j] = min({ board[i - 1][j - 1], board[i - 1][j], board[i][j - 1] }) + 1; 

나중에 다시 한 번 풀어봐야할 거 같다.