[프로그래머스 4단계] 알고리즘 36. 가장 큰 정사각형 찾기

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 36. 가장 큰 정사각형 찾기

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를 반환해 주면 됩니다.

#include<iostream>

#include<vector>

#include<utility>

using namespace std;

int findLargestSquare(vector<vector<char>> board)

{

    int answer = 0;

    return 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);

}

풀이:

나는 이 문제를 DP로 풀었다. DP란 Dynamic Programming 동적 계획법이라는 알고리즘 기법의 한 종류이다. 내가 세운 알고리즘은 다음과 같다.

1. 'O'를 1로 'X'를 0으로 바꾼다.

2. 가장 윗변, 왼쪽 변의 위치가 아닐 때 만약 'O'라면 해당 위치에서 가질 수 있는 가장 큰 정사각형 변의 길이를 저장한다.(DP)

3. 최대 사각형 넓이를 구한다.

먼저 주어진 board를 동적 계획법을 쉽게 적용할 수 있는 board로 바꿔 주어야 한다. 쉽게 말해 'O'라면 1로 'X'라면 0으로 바꿔 주는 것이다.

for (int i=0; i<board.size(); i++)

{

for (int j=0; j<board[i].size(); j++)

{

board[i][j] = (board[i][j] == 'O') ? 1 : 0;

//.....

}

}

이 문제의 핵심 DP에 해당하는 부분인 해당 위치에서 가장 큰 정사각형 넓이의 길이를 구하는 부분이다. 먼저 코드를 보자.

if (i == 0 || j == 0)

continue;

if (board[i][j] == 1)

{

board[i][j] = get_min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1;

answer = (answer > board[i][j]) ? answer : board[i][j];

}

먼저 해당 위치에서 3 부분을 검사해야 한다. 해당 위치의 윗부분, 왼쪽 부분 왼쪽-위 부분이다. 그 위치들은 이전에 이미 검사해서 각 위치에서 최대 사각형의 변의 길이를 저장하고 있다. 그 3개의 위치 중에서 최소값 + 1이 해당 영역이 가지는 최대 사각형 넓이의 길이이다. 무슨 말이냐면 주어진 board를 dp를 적용시키기 위해 0, 1을 갖는 board로 바꿨다면 다음과 같을 것이다.

1	2	3	4	5
0	1	1	1	0
0	1	1	1	1
0	0	1	1	1
0	0	1	1	1
0	0	0	0	0

dp를 적용할 때 3 위치를 검사해야 하는데 그 위치를 검사 못하는 가장 윗변과 왼쪽변은 dp에서 제외한다. 그럼 (1,1) 위치에서 dp를 적용해보자. 여기서 가질 수 있는 최대 정사각형 넓이는 1이다. (0, 0), (1, 0), (0,1)을 검사해보면  최소값은 0이다. 거기에 1을 더하면 최대 넓이 변의 길이 1이 나온다.

1	2	3	4	5
0	1	1	1	0
0	1	1	1	1
0	0	1	1	1
0	0	1	1	1
0	0	0	0	0

(1, 1) = min( (0, 0), (1, 0), (0, 1) ) + 1 = 0 + 1 = 1

그럼 이제 1, 2의 위치를 dp를 적용해보자. 왼쪽 위쪽 왼-위쪽이 모두 1이다. 따라서 2의 값을 갖는다. 이는 이 위치에서 가질 수 있는 정사각형의 한 변의 길이가 된다.

1	2	3	4	5
0	1	1	1	0
0	1	2	1	1
0	0	1	1	1
0	0	1	1	1
0	0	0	0	0

(1, 2) = min( (0, 1), (1, 1), (0, 2) ) + 1 = 1 + 1 = 1 ((1, 1)의 위치는 이미 검사를 진행하였다. )

이들을 이런식으로 적용해 나가면 다음과 같아질 것이다.

1	2	3	4	5
0	1	1	1	0
0	1	2	2	1
0	0	1	2	2
0	0	1	2	3
0	0	0	0	0

따라서 이 주어진 사각형에서 최대 넓이를 갖는 사각형은 9라는 것을 알 수 있다. 다음은 코드 전문이다.

int get_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 i=0; i<board.size(); i++)

{

for (int j=0; j<board[i].size(); j++)

{

board[i][j] = (board[i][j] == 'O') ? 1 : 0;

if (i == 0 || j == 0)

continue;

if (board[i][j] == 1)

{

board[i][j] = get_min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1;

answer = (answer > board[i][j]) ? answer : board[i][j];

}

}

}

    return answer * answer;

}

최근 개인적인 일로 알고리즘을 미루고 있었는데 오랜만에 풀어보니까 쉽지 않다;; 열심히 해야지!