728x90
시간 제한 1초, 메모리 제한 512MB
# 조건
- 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다.
- 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다.
- 그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다.
- 땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자.
- 이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미한다.
- 랜드씨의 땅에서 지을 수 있는 가장 큰 정사각형 목장의 한 변의 크기 L을 출력하시오.
# 접근 방법
- DP를 이용하여 풀어준다.
- records 테이블은 M행 N열을 오른쪽 아래 꼭짓점으로 가지는 정사각형 목장의 최대 한변 길이가 된다.
- 문제 해결의 핵심은, 현재 칸이 들판이라면 더 큰 정사각형을 만들기 위해서는 왼쪽, 왼쪽위 대각선, 위쪽 칸이 모두 들판이어야 한다.
- 그렇지 않다면 현재 칸을 오른쪽 아래 꼭지점으로 하는 제일 큰 정사각형은 1의 크기를 가지게 된다.
- 따라서, 위의 조건들을 체크하여 더 큰 들판을 만들 수 있다면, 위 / 왼 / 왼쪽 위 중 min 값을 찾아 +1을 하여 기록해주면 된다.
import sys
input = sys.stdin.readline
M, N = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(M)]
records = [[0] * N for _ in range(M)]
for i in range(N):
if arr[0][i] == 0:
records[0][i] = 1
for i in range(M):
if arr[i][0] == 0:
records[i][0] = 1
for i in range(1, M):
for j in range(1, N):
if arr[i][j] == 0:
if records[i-1][j-1] != 0 and records[i][j-1] != 0 and records[i-1][j] != 0:
records[i][j] = min(records[i-1][j-1], records[i][j-1], records[i-1][j]) + 1
else:
records[i][j] = 1
else:
records[i][j] = 0
print(max(max(records[i]) for i in range(M)))
728x90
'ALGORITHM > DP(동적 계획법)' 카테고리의 다른 글
[백준 18427번] 파이썬 - 함께 블록 쌓기 (1) | 2024.10.30 |
---|---|
[백준 1535번] 파이썬 - 안녕 (0) | 2024.10.30 |
[백준 13699번] 파이썬 - 점화식 (0) | 2024.05.29 |
[백준 11048번] 파이썬 - 이동하기 (0) | 2024.05.06 |
[백준 2670번] 파이썬 - 연속부분최대곱 (0) | 2024.04.04 |