[Python] 14925번 목장 건설하기

https://www.acmicpc.net/problem/14925

14925번: 목장 건설하기

---

 

24/01/29

 

 

2차원 DP문제로, 이전에 어떤 선배로부터 1915번 문제에 대한 풀이를 들은 적이 있었다.(물론 이 문제는 아직 해결하지 못한 상태다.)

 

그 접근 방법이 얼핏 생각이 나서 그 방식대로 접근을 했고, 맞았습니다를 받을 수 있었다.

---

 

문제 접근 방식:

 

 

DP테이블을 다음과 같이 정의했다.

 

$$DP[N][M] = N\textrm{행 }M\textrm{열을 오른쪽 아래 꼭짓점으로 가지는 정사각형 목장의 최대 한변 길이}$$

 

정사각형 목장 안에는 돌이나 나무가 들어가있어서는 안 된다는 제약 조건이 걸려있으므로, 만약 $N$행 $M$열이 들판이 아닐 때에는 $DP[N][M]$의 값은 $0$이 된다.

그 외의 경우, 즉, $N$행 $M$열이 들판일 경우를 생각해보자.

 

그렇다면, 현재 보는 칸의 위쪽 칸도, 왼쪽 칸도, 왼쪽 윗 방향의 대각선 칸도 전부 들판이어야만 이전 칸과 이어지는 정사각형 목장을 만들 수 있을 것이다.

 

만약 세 칸 중 하나라도 들판이 아니라면, 이전 칸과 이어지는 정사각형 목장을 만들 수 없고, 그럴 때에는 현재 칸 하나만 정사각형 목장으로 만들 수 있으므로 $DP[N][M]$의 값은 $1$이 된다.

 

만약 세 칸 모두 들판인 경우, $DP[N-1][M]$과 $DP[N][M-1]$, $DP[N-1][M-1]$의 값 중에서 가장 작은 값에서 현재 칸 하나를 더한 값이 $DP[N][M]$의 값이 될 것이다.

 

이 문제를 한 번 틀렸었는데, 세 칸 모두 들판인 경우를 잘못 생각해서 틀렸었다.

 

이 점에 유의하여 문제를 접근하면 쉽게 해결할 수 있을 것이다.

       

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 14925번 목장 건설하기
# DP
'''
접근 방법:
DP[N][M] = N행 M열을 오른쪽 아래 모서리로 가지는 정사각형 목장의 최대 한변 길이
현재 칸이 들판인 경우
왼쪽 칸과 위 칸, 대각선 왼쪽 위 모두 0이 아닌 경우
DP[N][M] = min(DP[N-1][M-1], ...) + 1
셋 중 하나가 0인 경우
DP[N][M] = 1
현재 칸이 들판이 아닌 경우
DP[N][M] = 0
'''
import sys
input = sys.stdin.readline

M, N = map(int, input().rstrip().split())
ground = [list(map(int, input().rstrip().split())) for _ in range(M)]
DP = [[0 for _ in range(N)] for _ in range(M)]
for i in range(N):
    if ground[0][i] == 0:
        DP[0][i] = 1
for i in range(M):
    if ground[i][0] == 0:
        DP[i][0] = 1
for i in range(1, M):
    for j in range(1, N):
        if ground[i][j] == 0:
            if DP[i-1][j-1] != 0 and DP[i-1][j] != 0 and DP[i][j-1] != 0:
                DP[i][j] = min(DP[i-1][j-1], DP[i-1][j], DP[i][j-1]) + 1
            else:
                DP[i][j] = 1
        else:
            DP[i][j] = 0
print(max(max(DP[i]) for i in range(M)))