[BOJ] 백준 1915번 : 가장 큰 정사각형 (JAVA)

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

 

 

 

 

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

 

 

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

 

 

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

 

 

풀이

부분 합을 이용한 완전 탐색 또는 다이나믹 프로그래밍으로 풀 수 있는 문제였습니다.

지금부터 두 가지 방식을 설명드리겠습니다.

 

 

부분 합을 이용한 완전 탐색 풀이

저는 처음에 사각형의 (1, 1) 부터 탐색하다가 게임판의 숫자가 1인 경우, 그 곳을 시작점으로 하여 가능한 사각형의 넓이를 구하는 식으로 생각했습니다.

 

가령 특정 지점의 숫자가 1이라고 하면, 그 숫자를 시작점으로 하여 2 x 2 사각형이 가능한지, 3 x 3 사각형이 가능한지, ... 순차적으로 쭉 탐색하는 것이었습니다.

 

단순히 위와 같이 코드를 짜서 제출하니까 시간 초과를 피할 수 없었습니다.

따라서, 여기서 시간을 줄이는 방법을 생각해 보았습니다.

 

위의 로직은 중복된 부분도 계속 더하는 성질이 있습니다. 그래서 미리 (x1, y1) 에서 (x2, y2) 까지의 부분 합을 모두 구하면 중복된 부분을 처음부터 계속 더하는 일 없이 바로 계산한 값을 사용할 수 있습니다.

 

1차원 배열의 부분 합은 psum[i] = psum[i - 1] + arr[i] 로 식이 간단하지만, 2차원 배열의 부분 합은 만만치 않습니다.

일단, (0, 0) 부터 시작하여 (i, j) 까지의 부분 합을 구하는 psum[i][j] 를 정의하는 방법을 알아봅시다.

 

결론부터 말하자면, psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i][j] + arr[i][j] 입니다.

왜 이렇게 식이 나오는지 아래 그림을 봅시다.

 

 

 

 

위에 파란색 사각형의 넓이가 psum[i][j]를 의미합니다.

하지만, 현재 psum[i][j]는 모르고, psum[i - 1][j], psum[i][j - 1], psum[i - 1][j - 1], arr[i][j]는 알고 있는 상태입니다.

 

 

 

 

위의 노란색 영역은 psum[i][j - 1]를 의미합니다.

 

 

 

 

위의 연두색 영역은 psum[i - 1][j] 입니다.

따라서 언뜻 보면, psum[i][j] = psum[i][j - 1] + psum[i - 1][j] + arr[i][j] 를 하면 부분 합을 구한 것처럼 보입니다.

 

 

 

 

하지만, psum[i - 1][j] 와 psum[i][j - 1]를 더하게 되면, 위와 같이 하늘색 영역인 psum[i - 1][j - 1]이 겹치게 됩니다.

따라서, 위의 겹치는 부분까지 고려하여

 

psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + arr[i][j]

 

를 취해야 합니다.

 

 

여기까지 psum[i][j] 를 정의하는 방법이었습니다.

이제, (0, 0) 에서 (i, j) 까지의 부분 합이 아닌, (x1, y1) 에서 (x2, y2) 까지의 부분 합을 구하는 방법을 알아봅시다.

 

 

 

 

위의 그림에서 파란색 영역으로 된 부분을 알고 싶습니다.

결론부터 말하자면, psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1- 1] 입니다.

 

(0, 0) 부터 (x2, y2) 의 부분 합인 psum[x2][y2] 에서 psum[x1 - 1][y2] 과 psum[x2][y1 - 1] 를 빼는데, 위의 노란색 영역을 2번 빼게 됩니다. 따라서 spum[x1 - 1][y1 - 1]을 추가적으로 더해주면, 우리가 원하는 (x1, y1) 에서 (x2, y2)의 부분 합을 구할 수 있습니다.

 

이론을 설명하느라, 꽤 돌고 돌아온 것 같습니다.

이제, 이것을 어떻게 활용하는지 봅시다.

 

문제에서 구하라고 한 것은 최대 사각형의 넓이입니다.

즉, 1x1, 2x2, 3x3, ... 중에 가능한 가장 큰 사각형을 찾으면 됩니다.

 

게임판의 (1, 1)부터 탐색을 시작하고, 중간에 게임판의 숫자가 1인 지점을 찾습니다.

그 칸을 시작점(i, j) 라 하고, 끝점은 (i + idx, j + idx)로 정합니다. (여기서 idx = 1 부터 시작합니다.)

 

만약, idx = 1일 때 위의 시작점부터 끝점까지의 부분 합이 4라면, 2 x 2 사각형을 만들 수 있음을 의미합니다.

따라서, idx를 1 증가시키고 다시 부분 합을 구합니다.

 

시작점 (i, j)과 끝점 (i + 2, j + 2) 사이의 부분 합을 구합니다. 부분 합이 9라면 3 x 3 사각형을 만들 수 있는 것이고, 9 미만이라면 중간에 0이 1개 이상 끼어 있는 것이므로 3 x 3 사각형을 만들 수 없습니다.

 

위의 과정을 (N, M) 까지 탐색을 진행하시면 됩니다.

아래 소스코드를 통해 확인해 보시길 바랍니다.

 

 

소스코드

 

 

다이나믹 프로그래밍을 이용한 풀이

위의 과정은 2차원 배열이라서 구간 합을 구하기도 만만치 않았고, 실행 시간 또한 느립니다.

하지만, 다이나믹 프로그래밍을 통해서 점화식을 세운다면, 훨씬 빠르게 문제를 해결할 수 있습니다.

 

식 자체는 매우 간단합니다.

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) 입니다.

 

특정 게임판의 숫자가 1인 경우, 그 게임판의 왼쪽, 위쪽, 왼쪽 대각선의 저장된 숫자 중 가장 작은 값에 1을 더한 값을 dp에 저장하는 것이죠.

 

만약에 특정 게임판의 숫자에 대하여 세 가지 방향 중 0이 존재한다면, 가능한 최대 사각형은 1 x 1 인 것이고, 세 가지 방향 중 가장 작은 값이 1 이라면, 가능한 최대 사각형은 2 x 2 인 것입니다.

 

단, dp[1][1] = arr[1][1] 를 그대로 따라가야합니다. 첫 시작점은 세 가지 방향을 따질 수 없기 때문이죠.

아래 소스코드를 통해 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.