[BOJ][🟡4][백준#14925] 목장 건설하기

문제 출처

BAEKJOON Online Judge #14925

문제

랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다.  그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다.  땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자.  이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미한다.  랜드씨의 땅에서 지을 수 있는 가장 큰 정사각형 목장의 한 변의 크기 L을 출력하시오.

입력

M N M x N 행렬

1 <= M <= 1000 1 <= N <= 1000

출력

L

예제

입력

6 6
0 0 0 1 0 0
0 0 0 2 1 0
0 0 2 0 0 0
0 1 0 0 0 0
2 0 0 0 0 0
0 0 0 0 0 0

출력

3

My Sol

I, J = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(I)]
mat_h = [[0]*(J+1) for _ in range(I+1)]
mat_v = [[0]*(J+1) for _ in range(I+1)]

for i in range(1, I+1):
    for j in range(1, J+1):
        if mat[i-1][j-1]: continue
        mat_h[i][j] = mat_h[i][j-1] + 1

for j in range(1, J+1):
    for i in range(1, I+1):
        if mat[i-1][j-1]: continue
        mat_v[i][j] = mat_v[i-1][j] + 1

dp = [[0]*(J+1) for _ in range(I+1)]
for i in range(1, I+1):
    for j in range(1, J+1):
        if mat[i-1][j-1]: continue
        dp[i][j] = min(mat_v[i][j], mat_h[i][j], dp[i-1][j-1]+1)

maxx = 0
for i in range(1, I+1):
    for j in range(1, J+1):
        if maxx < dp[i][j]:
            maxx = dp[i][j]
print(maxx)

1. 입력을 처리해준다.
2. mat 2차원 배열의 가로 세로의 연속된 0의 길이를 각각 mat_h와 mat_v에 표시해준다.
3. dp 배열에 현재 위치의 가로 세로 연속 길이, 그리고 왼쪽 위 최대길이+1 값 중 최솟값을 저장한다. 이는 곧 현재 위치를 오른쪽 아래 점으로 하는 정사각형의 최대 변 길이이다.
4. 모든 dp 배열에 대해 최댓값을 구해 출력한다.

결과

맞았습니다!!

모범답안

출처

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if board[i-1][j-1]:
            dp[i][j] = 0
        else:
            dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            
print(max(map(max, dp)))

현재 위치에 0이 아니라면 dp에 0을 두고, 그렇지 않다면 위, 왼쪽, 왼쪽 위 3방향의 dp 값 중 최솟값 +1을 현재 dp에 저장한다.

연속된 0을 계산하는 mat_v, mat_h의 과정이 없기 때문에 훨씬 빠른 연산속도를 가질 수 있으며, 이미 dp 배열에 0으로 초기화되었으므로 board[i-1][j-1] 이 0이 아니라면 dp에 0을 재할당하는 것이 아니라 continue 하는 것이 메모리 측면이나 시간 측면에서도 더 유리할 듯 싶다.

2차원 배열 내의 최댓값을 구하는 것을 print(max(map(max, dp)))로 굉장히 간결하게 구현했다.