[알고리즘] DP-가장 큰 정사각형 찾기

문제 해결 전략

DP 파악

DP는 작은 문제로 큰 문제 해결

작은 문제의 답을 memory에 적재

#include<iostream>
#include<vector>
#include<utility>
#include<math.h>
using namespace std;
 
 
//x,y에서의 최대 변의 길이를 저장하는 변수
vector<vector<int>> dp(10001, vector<int>(10001,0));
 
 
int _min(int a, int b, int c)
{
    a = a  < b ? a : b;
    return a = a < c ? a:c;
}
int findLargestSquare(vector<vector<char>> board)
{
    int answer = 0;
    int col = board[0].size();
  int row = board.size();
  int max = -1;
 
 
  for (int x = 0 ; x < col ; x++ )
  {
    for (int y = 0 ; y < row ; y++ )
    {
          dp[y][x] = board[y][x] == 'O' ? 1 : 0;
          if (board[y][x] == 'O' && y !=0 && x != 0)
 
            dp[y][x] = _min(dp[y-1][x], dp[y][x-1], dp[y-1][x-1]) + 1;
          if(max < dp[y][x])
            max = dp[y][x];
    }
  }
 
  answer = max * max;
  /* Debug
  for (int x = 0 ; x < row; x++)
  {
    for (int y = 0; y < col; y++)
    {
      cout << dp[x][y] << ' ';
    }
    cout << endl;
  }*/
 
 
    return answer;
}
int main()
{
 
 
    vector<vector<char>> board{
                {'X','X','O','O','X','O','X'},
                {'X','X','O','O','O','O','O'},
                {'O','X','O','O','O','O','X'},
                {'O','O','O','O','O','O','O'},
            {'O','X','O','O','X','O','X'},
            {'X','O','O','O','O','O','O'},
              {'X','X','O','O','O','O','O'}};
 
    //아래는 테스트 출력을 위한 코드입니다.
    cout<<findLargestSquare(board);
}