[문제]
부산 시민의 숙원사업인 돔 야구장을 부산 외곽 지역에 건립하고자 한다. 야구장 건립을 위해서 볼파크 공사 예정지는 아래 그림과 같이 $N \times M $ {0,1} 행렬(matrix)로 표시되며, 공사 예정지 내의 $k \times k$ 크기의 정방형 공간에 돔구장을 지으려고 한다. 그런데 이 지역의 어떤 지점에는 큰 암반이나 물구덩이가 있어서 해당 지점에서는 공사할 수가 없다. 아래 그림에서 $M_{i,j} = 1$ 은 위치 $(i , j)$에 지점에 엄청난 크기의 돌, 보호해야 할 정도의 큰 수목, 깊은 웅덩이 등의 장애물이 있음을 나타낸다. 그리고 $M_{i,j} = 0$ 은 해당 지점 $(i , j)$ 을 그대로 활용할 수 있음을 나타낸다.
우리는 이 예정 지역에 가장 큰 완전 $k \times k$ 정방형 공간이 어디에 있는지 모두 찾아내야 한다. 완전 $k \times k$ 정방형 공간이란 모두가 ’0‘인 부행렬(submatrix)를 말한다. 물론 그 정방형 야구장의 평지 크기($k$)는 최대가 되어야 한다.
아래 그림-1에서 볼 때 (a)의 경우에 가장 큰 완전 정방형 야구장의 크기는 $5 \times 5$이며 가능한 장소 중 하나가 파란색으로 표시되어 있다. 그림-1(b)의 경우, 가장 큰 야구장 크기는 $5 \times 5$ 이며 가능한 장소 중 2 군데가 초록색 / 주황색으로 표시되어있다. 그림 (b)와 같이 점유공간이 서로 겹쳐도 다른 장소로 취급한다.
[입출력]
입력 파일 ballpark.inp 의 첫 줄에는 볼파크 후보지 공간의 크기를 나타내는 2개의 정수 $N, M$이 제시된다. $N$은 세로 길이, $M$은 가로 길이이며 $10 \leq N,M \leq 1000$이다. 이어서 각 개의 줄에 {0,1}로만 구성된 길이 인 이진 문자열(binary string)이 주어진다. 그 순서는 위에서 아래로 주어진다. 즉 제일 처음 나오는 줄(row)는 후보지 공간의 밑에서부터 $N$번째 row의 상황을 제시한다. 아래 예를 잘 비교해서 보시오.
여러분은 이 입력 파일을 읽고 후보지 공간에서 가장 큰 완전 $k \times k$ 정방형 공간을 모두 찾아야 한다. 출력은 가능한 최대 가능 공간의 크기 을 제시한 다음 가능한 지역의 개수 $r$ 을 같은 줄에 이어서 $k\,r$형태로 출력한다. 이 볼파크 예정지 $k \times k$ 공간들은 일부분이 서로 겹쳐도 상관없다.
두번째 줄부터 이어지는 $r$개의 줄에 여러분이 찾아낸 완전 $k \times k$ 공간의 왼쪽 아래 좌표 $(x, y)$를 $x\,y$로 출력한다. 단, 하나 이상일 경우에는 $x\,y$ 는 그 순서의 사전식 순서가 빠른 것부터 출력한다. 즉 $x$ 가 더 작은 순서가 먼저 나타나야하고 만일 좌표가 같다면 $y$ 의 오름차순 순서로 출력한다.
[예제]
|
ballpark.inp |
ballpark.out |
|
12 12 //N, M 010000000000 000000000000 000000100000 000100000100 000000000000 100000000000 000000000000 000000000001 000000100000 000000001000 010000100000 000000000000 |
5 3 //k=5, r=3 2 3 // submatrix 2 4 5 5
|
|
11 13 //N=11,M=13 0001000000000 0100000000000 0000000100000 0000000000100 0000000100000 0000000000000 0010100000000 0000000000011 0000000000000 0100000000000 0000000100000 |
5 3 //k=5, r=3 3 6 6 2 7 2
|
[풀이] $O(NM + K) or O(NM)$
문제를 보자마자 $O(NM + K)$의 풀이가 생각났다. 부분합을 이용해서, 현재 위치 $(x,y)$에서 $k$크기의 정사각형을 채울 수 있는지 판단이 $O(1)$만에 가능하기 때문에, $k$를 업데이트 해주면서 체크하면 간단하게 풀린다.
부분합 $pSum[y][x]$를 $(0,0)$에서 $(y,x)$까지의 합이라 정의하자. $(y,x)$에서 $k$크기의 정 사각형을 만들 수 있는지는
$pSum[y][x] - pSum[y - k + 1][x] - pSum[y][x - k + 1] + pSum[y - k + 1][x - k + 1]$이 되므로 $O(1)$에 판단 가능하고, 부분합 $pSum[y][x]$는 $O(NM)$만에 구해지므로, $k$를 업데이트하는 시간까지 고려하여, $O(NM + K)$이다.
근데, 이거 처음 ps공부 시작할 알린이였던 시절 풀어본 문제임을 정확히 기억한다. dp라는걸 처음 접했을 때, 내 기억으로 종만북에서 소개되었다. 그래서, 다시한번 dp로 풀어보았다.
$dp[y][x]$를 $(y,x)$에서 만들 수 있는 최대 정사각형의 크기라고 정의해보자. 만약 $arr[y][x]$가 1이라면 명백히 $dp[y][x]$는 0이다.(basecase)
만약, $arr[y][x]$가 0이 라면, 최대 정사각형의 크기는 $(y - 1, x)$, $(y, x - 1)$,$(y - 1,x - 1)$에서 최대 정사각형의 크기 중 작은 값보다 1이 크다. 왜 그런지는 직관적으로, 혹은 조금만 그려봐도 왜 그런지 단번에 이해가 될것이다.
너무 간단한 dp문제지만, 알고리즘 공부가 처음인 사람이 보면 꽤 오래 걸릴 문제다.'
