# 프로그래머스 : 가장 큰 정사각형 (Level 4)

[문제]


O와 X로 채워진 표가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 O로 이루어진 가장 큰 정사각형을 찾아 넓이를 반환하는 findLargestSquare 함수를 완성하세요. 예를 들어
12345
XOOOX
XOOOO
XXOOO
XXOOO
XXXXX
가 있다면 정답은
12345
XOOOX
XOOOO
XXOOO
XXOOO
XXXXX
가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

[풀이]


 이 문제는 DP(Dynamic Programming : 동적 계획법)를 이용하는 대표적인 문제다.
(DP에 대한 포스팅은 추후에 정리하여 올리도록 하겠다)
사실 DP에 대해 잘 모르기 때문에.. 이 문제를 푸는데 굉장히 애를 먹었다.

 우선 DP보다도 이 문제를 접근하는 방법에 대해 알아야하는데, 이 문제를 예로 들어보자.

XOOOX
XOOOO
XXOOO
XXOOO
XXXXX

 위와 같은 5X5 배열이 있다고 가정하자. 
우리가 알아야 하는 것은 'O' 표시가 된 배열이 포함된 최대 정사각형의 크기(넓이)를 구하는 것인데,
해당 배열 좌표를 기준으로 '어떤 방향으로 정사각형을 확인할지'를 정하면 된다.

 다른 홈페이지에서 볼 수 있는 대부분의 해설들과 마찬가지로, 
'해당 배열 좌표를 기준으로 상, 좌, 상좌의 좌표'를 확인하면 된다.

 대신 그러려면 [0,0] ~ [0,n]의 배열 원소들과 [0,0] ~ [n,0]의 배열 원소들은 계산할 수 없게 되는데,
이를 해결하기 위해 n+1 X n+1 크기의 배열을 생성해주고, 실제 값은 [1,1]부터 [n,n]까지 할당한다.

 그러므로 이를 그림으로 설명하면,

 XXXXXX
XXXXXX
XXXXXX
XXXXXX
XXXXXX
XXXXXX

 모두 X로 채워진 6X6 배열을 만들고, 

 XXXXXX
XXOOOX
XXOOOO
XXXOOO
XXXOOO
XXXXXX

 이런식으로 새로 생성된 배열의 안쪽에 원래 구해야 하는 배열을 넣어주면 된다.

새로 생성된 6X6 배열을 NewArray라고 할 때, 계산 과정은 다음과 같다.
그 전에 O, X를 각각 1,0으로 치환한다. (치환하는 이유는 아래에 밝힌다)
NewArray의 검사 범위는 아래 음영으로 표현된

 XXXXXX                000000
XXOOOX               001110
XXOOOO               001111
XXXOOO      ->      000111
XXXOOO               000111
XXXXXX                000000

 즉, 문제에서 제공된 실제 배열 구간만 비교한다.

  1. NewArray[1,1]부터 NewArray[6,6]까지 검사하던 중
  2. NewArray[n,n] = 1일 때
  3. NewArray[n-1, n], NewArray[n-1,n-1], NewArray[n,n-1] 의 값 중 최소 값을 확인하고
  4. NewArray[n,n]에 3에서 구한 최소값 + 1을 대입
하면 된다. 

수학적으로 표현하는 방법은 잘 모르지만, 이렇게 하면
기존 배열을 Array라고 할 때, NewArray[n,n] = Array[n-1,n-1]이 되므로.
결국 Array[n-1,n-1]을 '최 하단 우측'으로 두는 정사각형으로 이루어진 배열의 갯수가 된다.

이를 코드로 표현하면 다음과 같다.

int Min(int a, int b, int c) {
    a = a < b ? a: b;
    return a < c ? a : c;
}

int findLargestSquare(vector<vector<char>> board)
{
    int answer = 0;
    vector<vector<int>> intboard
                   (board.size()+1, vector<int>(board[0].size()+1));
    vector<vector<int>> dp
                   (board.size()+1, vector<int>(board[0].size()+1));
    
    int x = board.size();
    int y = board[0].size();
    int i,j;
    
    for(i=0; i<x; i++) {
        for(j=0; j<y; j++) {
            if(board[i][j] == 'O')intboard[i+1][j+1] = 1;
            else intboard[i+1][j+1] = 0;
        }
    }
    for(i=1; i<=x; i++) {
        for(j=1; j<=y; j++) {
            if(intboard[i][j] == 1) {
                dp[i][j]=Min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
                answer = answer > dp[i][j] ? answer : dp[i][j];
            }
        }
    }
    
    return answer*answer;
}

Min 함수는 주어진 3개의 배열 값 중 가장 작은 값을 반환해주는 함수다.

위의 findLargestSquare 함수를 통해 반환된 값은
특정 배열 좌표를 최하단우측으로 두었을 때, 해당 배열 좌표를 이용하여 생성될 수 있는 정사각형 갯수
가 된다.

그러므로 넓이는 answer * answer 가 되므로 위를 이용하여 구할 수 있다.


사실 DP에 대해서도 잘 모르지만, 이 경우 문제의 접근이 어려워서 애를 먹었다.
앞으로 이런 문제가 나오는 경우 해결 방법을 더 쉽게 접근해 볼 수 있을 것 같다.

댓글

댓글 쓰기