[#24][알고리즘] 가장 큰 정사각형 찾기

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

문제 링크(https://programmers.co.kr/learn/challenge_codes/187)

C++풀이

#include<iostream> #include<vector> #include<utility> #include<algorithm> using namespace std; int findLargestSquare(vector<vector<char>> board) {   int answer = -2;   int dp[1000][1000] = {0};      //숫자 0, 1로 변환   for(int i = 0; i < board.size(); i++)     for(int j = 0; j <board[0].size(); j++){         if(board[i][j] == 'O')           dp[i][j] = 1;     }       for(int i = 1; i < board.size(); i++)     for(int j = 1; j < board[0].size(); j++){       if(dp[i][j] == 1){       dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1], dp[i-1][j]))+1;       answer = max(dp[i][j], answer);       }     }   // 배열dp에 저장된 최대값의 제곱을 리턴   answer = pow(answer,2);   return answer; } int main() {          vector<vector<char>> board{                 {'X','O','O','O','X'},                 {'X','O','O','O','O'},                 {'X','O','O','O','O'},                 {'X','X','X','X','X'},                 {'X','X','X','X','X'}};     //아래는 테스트 출력을 위한 코드입니다.     cout<<findLargestSquare(board); } Colored by Color Scripter

cs

dp배열의 값이 1일 때(입력 값 O)만 정사각형 찾기 검사 시작
dp[1][1]부터 dp[4][4]에 대하여
dp[i][j] = dp[i][j] 기준 왼쪽, 위쪽, 왼쪽대각선 값을 확인하여 가장 작은 값 + 1(원래 가지고있던 값)

• i=1, j=1일 때

    dp[1][1] = dp[1][0], dp[0][1], dp[0][0] 중 최소값 + 1 = 0 + 1 = 1
    1 * 1 크기의 정사각형이 있음

• i=1, j=2일 때

    dp[1][2] = dp[1][1], dp[0][2], dp[0][1] 중 최소값 + 1 = 1 + 1 = 2
    2 * 2 크기의 정사각형이 있음

• i=1, j=3일 때

    dp[1][3] = dp[1][2], dp[0][3], dp[0][2] 중 최소값 + 1 = 1 + 1 = 2
    2 * 2 크기의 정사각형이 있음

 => dp[i][j]를 완성하며 최대값을 찾음( answer )
정사각형의 넓이를 return해야하므로 answer 제곱을 리턴