프로그래머스 - 가장 큰 정사각형 찾기 [C++]

이 문제는 다이나믹 프로그래밍의 아이디어를 통해 푼다. 이 문제를 고민하다가 아무런 아이디어가 떠오르지 않아 검색을 하고 풀었다. 

 

이 문제의 핵심은 현재 위치를 (y, x) 라고 한다면 현재 위치의 숫자가 1인 경우, 왼쪽, 왼쪽 위, 위쪽이 모두 1이어야 한 변의 길이가 2, 넓이가 4인 정사각형이 된다는 사실이다.

 

한 변의 길이가 3인 2차원 배열에서의 예시를 보면

// 초기 상태
1 1 0
1 1 1
1 1 1

// (1, 1) 부분의 계산
1 1 0
1 2 1
1 1 1

// (1, 2) 부분의 계산
1 1 0
1 2 1
1 1 1

// (2, 1) 부분의 계산
1 1 0
1 2 1
1 2 1

// (2, 2) 부분의 계산
1 1 0
1 2 1
1 2 2

와 같이 나타낼 수 있다.

 

각 배열의 요소가 나타내는 것은 해당 위치에서의 최대 정사각형의 한 변의 길이를 나타내게 된다.

즉, board[y][x] = min(board[y - 1][x], board[y][x - 1], board[y - 1][x - 1]) + 1 로 놓고 계산하면 쉽게 풀 수 있다.

 

왜 인접한 세 위치 중 최소를 구하고 1을 더하는지 궁금했는데, 생각해보면 당연했다.

1을 더하는 부분에 있어서는 (1, 2) 부분에서 보면 해당 위치에서 가능한 최대 정사각형의 길이는 1이다. 이는 애초에 2차원 배열을 순회할 때 자신이 1임을 검사한 뒤에 동작하므로, 다른 인접한 부분이 모두 0이어도 자기 자신이 1이므로 1이 저장되어야 한다. 그러므로 1을 더해주는 것이다.

 

인접한 세 위치 중 최소를 구하는 것이 약간 모호했는데, 세 부분에서 어느 하나라도 작은 것이 있다는 것은 인접한 세 위치의 배열 값을 계산할 때 작은 부분의 위치에서 어딘가 0이 존재했다는 뜻으로 이해했다. 정사각형이 되려면 정사각형 안이 모두 1이어야 하므로, 최소를 찾은 뒤 + 1을 해줘야 정답이 나오게 된다.

 

이런 문제를 코딩 테스트에서 만나면 쉽지 않을 것 같다..

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 1000

void calculate(vector<vector<int>>& board) {
    int rowSize = board.size();
    int columnSize = board[0].size();
    
    for (int y = 1; y < rowSize; y++) {
        for (int x = 1; x < columnSize; x++) {
            if (board[y][x] == 0) {
                continue;
            }
            
            board[y][x] = min(board[y - 1][x], min(board[y][x - 1], board[y - 1][x - 1])) + 1;
        }
    }
}

int findAnswer(vector<vector<int>>& board) {
    int result = 0;
    int rowSize = board.size();
    int columnSize = board[0].size();
    
    for (int y = 0; y < rowSize; y++) {
        for (int x = 0; x < columnSize; x++) {
            result = max(result, board[y][x]);
        }
    }
    
    return result;
}

int solution(vector<vector<int>> board)
{
    int rowSize = board.size();
    int columnSize = board[0].size();
    
    if (rowSize == 1 && columnSize == 1) {
        return board[0][0];
    }
    
    calculate(board);
    int answer = findAnswer(board);
    
    return answer * answer;
}