[백준] 1915 가장 큰 정사각형

 

이번 문제에서 가장 큰 정사각형을 구하기 위해서 모든 경우의 수를 하나씩 탐색한다면, 이 문제를 풀 수가 없다. 최대 크기의 사각형에서 모든 경우의 수를 다 구하기 위해서는 방법이 무지막지하게 많아진다.

그렇다면 다른 방법은 무엇이 있을까? 답은 다이나믹 프로그래밍을 이용하는 것이다. 다이나믹 프로그래밍을 이용하여 시간복잡도 O(NM) 으로 풀이가 가능하다. 예시를 보면서 풀이 방법에 대하여 천천히 알아보자.

 

 

예시로 보여준 그림이 있다. 탐색 순서는 위에서 아래로, 좌측에서 우측으로 이동하며 탐색한다. dp 배열은 입력으로 들어온 배열과 크기가 같다.

 

 

첫번째 붉은색 상자를 보자. 상자 안에는 0이 2개, 1이 2개 있다. 해당 칸은 정사각형을 이룰 수 있는가? 답은 이룰수 없다. 이렇게 된 결과를 dp 배열(저장위치 : 우측 하단 칸)에 저장한 다음, 다음 경우의 수로 넘어가자.

 

 

여기서 붉은색 상자는 정사각형이 가능한가? 답은 그렇다. 모든 칸에 1이 존재하므로 정사각형을 만들 수 있다. 하지만 여기서 칸에 1이 존재하는 것은 입력으로 들어온 판이 아니라 dp에 있는 칸을 이용하여 알아내는 것이다. 한 변의 길이가 2인 정사각형 제작이 가능하므로, dp배열에 2를 저장한다. 저장위치는 우측 하단이다.

 

 

여기서는 우측 하단의 칸이 0으로 되어 있다. 이러한 경우에는 정사각형 제작이 불가능하다. dp 배열에 0을 저장한다.

 

이렇게 검사하다 보면, 두 가지 규칙이 보인다. 입력 배열의 우측 하단의 값이 0이면 정사각형을 만들 수 없다. 그리고 우측 하단의 값이 0이 아닐 시, 우측 하단을 둘러싼 3개 값의 최소값 + 1이 한변의 길이가 되는 것을 알 수 있다. 다음 그림은 dp를 실행한 배열의 모습이다.

 

 

dp를 실행한 결과에서 제일 큰 값^2 을 출력하면 답이 나오게 된다.

 

이 문제는 dp로 풀 수 있지만, 생각하는 데 많은 어려움이 있었고, 여러 질문을 참고해 문제를 풀었다. dp 문제는 풀어도 풀어도 끝이 없는것 같다. 오늘은 이 문제를 풀며 생각을 많이 하게 되었다.