가장 큰 정사각형 구하기

문제

O와 X로 채워진 표가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 O로 이루어진 가장 큰 정사각형을 찾아 넓이를 반환하는 findLargestSquare 함수를 완성하세요. 예를 들어

1	2	3	4	5
X	O	O	O	X
X	O	O	O	O
X	X	O	O	O
X	X	O	O	O
X	X	X	X	X

가 있다면 정답은

1	2	3	4	5
X	O	O	O	X
X	O	O	O	O
X	X	O	O	O
X	X	O	O	O
X	X	X	X	X

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

풀이

해당 문제는 프로그래머스 뿐만 아니라 백준을 비롯한 다양한 알고리즘 연습 사이트에 등장하며 코딩 테스트에서도 종종 나오는 단골 문제 중 하나이다.(물론 응용되지만..)

간단하게 요약하면 현재 지점의 좌, 상, 좌-상 지점으로 판단한다

방식은 이렇다.

현재 지점을 기준으로 좌측 지점, 상단 지점, 좌상단 지점의 값 중 가장 작은 값을 구하고

그 값에 현재 값을 더한다.(이 부분은 코딩을 통해 + 1로 더하는 것으로 변형할 수 있다. Line 20과 22 참고)

그리고 전체 사각형에서 최대 값을 구하고(Line 23. 기준 값(0)을 잡고 가장 큰 값이 나오면 갱신하면 된다..)그 값을 제곱하여 반환한다.

따라서 당연히 좌상과 좌, 상의 값을 구할 수 없는 지점을 제외하고 반복문을 시작해야하므로

for(int i = 1 …)과 같은 식으로 작성해준다.

다만 위 코드에서는 X와 O라는 문자를 0 또는 1로 대체하여 저장하기 위해서 위와 같이 0부터 시작하였다. 대신 &&로 if문에서 조건을 추가하였다.

소스 코드

#include <iostream>
#include <vector>

using namespace std;

int _MIN(int a, int b, int c)
{
  return (a > b) ? ((b > c) ? c : b) : ((a > c) ? c : a);
}

int findLargestSquare(vector<vector<char>> board)
{
  int answer = 0;

  for (int row = 0; row < board.size(); row++)
  {
    for (int col = 0; col < board[0].size(); col++)
    {
      board[row][col] = (board[row][col] == 'O') ? 1 : 0;
      if (board[row][col] != 0 && row != 0 && col != 0)
      {
        board[row][col] = _MIN(board[row - 1][col], board[row][col - 1], board[row - 1][col - 1]) + 1;
        answer          = (answer < board[row][col]) ? board[row][col] : answer;
      }
    }
  }

  return answer * answer;
}
int main()
{
  vector<vector<char>> board{
    { 'X', 'O', 'O', 'O', 'X' },
    { 'X', 'O', 'O', 'O', 'O' },
    { 'X', 'X', 'O', 'O', 'O' },
    { 'X', 'X', 'O', 'O', 'O' },
    { 'X', 'X', 'X', 'X', 'X' }
  };

  // 아래는 테스트 출력을 위한 코드입니다.
  cout << findLargestSquare(board);
}

출처

알고리즘 연습 Level 4 | 프로그래머스