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

Gurumee 2018. 5. 9. 12:00

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(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 동적 계획법이라는 알고리즘 기법의 한 종류이다. 내가 세운 알고리즘은 다음과 같다.

'O'를 1로 'X'를 0으로 바꾼다.
가장 윗변, 왼쪽 변의 위치가 아닐 때 만약 'O'라면 해당 위치에서 가질 수 있는 가장 큰 정사각형 변의 길이를 저장한다.(DP)
최대 사각형 넓이를 구한다.

먼저 주어진 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로 바꿨다면 다음과 같을 것이다.

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

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

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

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

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

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

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

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

2	3	4	5
1	1	1	0
1	2	2	1
0	1	2	2
0	1	2	3
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;
}

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

728x90

저작자표시 (새창열림)