Funcia
Lv.2dpgrid

가장 넓은 정사각형 잔디밭

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

공원 관리소가 공원 부지를 격자로 나눈 지도 grid를 가지고 있습니다. grid[i]는 i번째 줄을 나타내는 문자열이고, 각 글자는 잔디가 자란 칸이면 '1', 흙이나 돌이 드러난 칸이면 '0'입니다.

돗자리 축제를 위해 잔디 칸으로만 이루어진 정사각형 구역 중 가장 넓은 곳을 찾으려 합니다. 정사각형의 변은 격자선과 나란해야 합니다.

가능한 가장 큰 정사각형의 **넓이(칸 수)**를 반환하세요. 잔디 칸이 하나도 없으면 0입니다.

입출력 예

gridresult
["10100", "10111", "11111", "10010"]4
["01", "10"]1
["0"]0

입출력 예 설명

예 1 — 1행 2열부터 2행 3열까지(0부터 셈)의 2×22 \times 2 구역이 모두 잔디입니다. 3×33 \times 3 잔디 구역은 없습니다.

예 2 — 잔디 칸이 대각선으로만 놓여 있어 1×11 \times 1이 최대입니다.

예 3 — 잔디 칸이 없습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(grid: string[]) → int

제한 사항

  • 1≤H=1 \le H = grid.length ≤1,000\le 1{,}000
  • 1≤W=1 \le W = grid[i].length ≤1,000\le 1{,}000, 모든 줄의 길이는 같습니다.
  • grid[i]는 '0'과 '1'로만 이루어져 있습니다.

기대 복잡도

시간
O(HW)
공간
O(W)

입출력 예

grid기대 출력
["10100","10111","11111","10010"]4
["01","10"]1
["0"]0

힌트

힌트

칸마다 정사각형을 한 줄씩 키워 보며 확인하면, 잔디가 빽빽한 지도에서는 칸 하나에만 O(min⁡(H,W)2)O(\min(H, W)^2)이 들어 효율성 테스트를 통과할 수 없습니다.

side[i][j] = "칸 (i, j)를 오른쪽 아래 꼭짓점으로 하는 가장 큰 잔디 정사각형의 변 길이"로 두세요. (i, j)가 잔디라면

side[i][j]=1+min⁡(side[i−1][j], side[i][j−1], side[i−1][j−1])side[i][j] = 1 + \min(side[i-1][j],\ side[i][j-1],\ side[i-1][j-1])

입니다. 세 이웃 중 가장 작은 정사각형이 확장을 가로막기 때문입니다. 흙 칸은 0입니다. 표를 한 번 채우면 O(HW)O(HW)이고, 답은 가장 큰 side의 제곱입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.