구멍

과학자들이 넓은 숲을 관측하려고 한다. 이들은 작은 센서를 숲에 공중 투하할 계획이다. 투하 과정에는 예측할 수 없는 조건이 많아서 각 센서는 숲 안의 임의의 위치에 떨어진다. 센서가 모두 떨어지고 나면 숲에는 센서가 하나도 없는 정사각형 영역이 남는다. 이런 영역을 구멍이라고 부른다.

구멍은 작을수록 좋고, 센서를 아주 많이 뿌리면 그렇게 만들 수 있다. 하지만 센서는 비싸다. 그래서 과학자들은 큰 구멍이 생길 확률이 충분히 낮아지려면 센서를 몇 개나 뿌려야 하는지 컴퓨터 시뮬레이션으로 알아보기로 했다. 이 시뮬레이션에는 센서의 위치를 받아 가장 큰 구멍의 크기를 출력하는 서브루틴이 필요하다. 시뮬레이션은 매개변수를 바꿔 가며 여러 번 반복하므로 서브루틴은 아주 빨라야 한다. 이 서브루틴을 작성하는 것이 여러분이 할 일이다.

0과 1로 이루어진 $n \times n$ 배열 $A$를 생각하자. 다음 두 조건을 만족하면 $A$의 $(x, y)$에 너비가 $d$인 구멍이 있다고 한다.

• $i = x, x+1, x+2, \dots, x+d-1$이고 $j = y, y+1, y+2, \dots, y+d-1$인 모든 $(i, j)$에 대해 $A[i, j] = 0$이다.
• $x + d - 1 < n$이고 $y + d - 1 < n$이다.

즉 $(x, y)$에서 시작하는 너비 $d$짜리 정사각형 안의 값이 모두 0이다. 배열의 인덱스는 0부터 시작한다.

배열 $A$가 주어지면 가장 큰 구멍의 너비를 구하라.

입력은 배열 $A$를 나타낸다.

첫째 줄에 배열의 너비 $n$이 주어진다. $n$은 1,024 이하의 양의 정수다. 둘째 줄에는 배열에 들어 있는 1의 개수 $k$가 주어진다. 이어지는 $k$개의 줄에는 값이 1인 칸이 한 줄에 하나씩 주어진다. 각 줄에는 정수 $x$와 $y$가 주어지며, $A[x, y] = 1$이라는 뜻이다.

$n$은 1,024까지 커질 수 있으므로 그 크기의 배열도 충분히 빠르게 처리해야 한다.

가장 큰 구멍의 너비를 정수 하나로 출력한다. 배열에 구멍이 하나도 없으면 0을 출력한다.

아래 그림은 첫 번째 예제의 배열이다. $A[i, j]$는 $i$번째 행, $j$번째 열에 있고, 화살표는 $A[3, 7]$의 위치를 가리킨다.

이 배열에서 $(0, 0)$에는 너비 3인 구멍이 있지만 너비 4인 구멍은 없다. 가장 큰 구멍은 너비가 5이고 $(1, 2)$에 있다. 그림에서 강조한 정사각형이 그 구멍이다.

가장 큰 구멍을 빠르게 찾는 방법은 여러 가지다. 아래는 서로 다른 두 방법의 힌트다.

힌트 1: 다음 두 값을 생각해 보자.

• $d_1$: $(1, 1)$에 놓을 수 있는 가장 큰 구멍의 너비
• $d_2$: $(2, 2)$에 놓을 수 있는 가장 큰 구멍의 너비

$d_1$과 $d_2$는 어떤 관계인가? $d_2$를 알고 있다면 $d_1$을 빠르게 계산하는 방법이 있는가?

힌트 2: 다음 두 값을 생각해 보자.

• $s_1$: $(0, 0)$에서 시작하는 너비 7인 정사각형 안에 있는 1의 개수
• $s_2$: $(0, 1)$에서 시작하는 너비 7인 정사각형 안에 있는 1의 개수

$s_1$과 $s_2$는 어떤 관계인가? $s_1$을 알고 있다면 $s_2$를 빠르게 계산하는 방법이 있는가?