[Gold IV] 목장 건설하기 - 14925

문제 링크

성능 요약

메모리: 46928 KB, 시간: 1348 ms

분류

다이나믹 프로그래밍

문제 설명

랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다.

그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다.

땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자.

이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미한다. 랜드씨의 땅에서 지을 수 있는 가장 큰 정사각형 목장의 한 변의 크기 L을 출력하시오.

입력

M N
M x N 행렬

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

출력

L

풀이

아이디어1

1X1부터 $min(n,m) \times min(n, m)$ 까지 크기를 늘려가면서 탐색한다.
1. 기준이 될 왼쪽 위의 한 점을 구하고, 장애물이 나오기 전까지 늘려나간다.
2. 장애물이 나오지 않는 가장 최대의 값을 해당 그리드에 모두 메모이제이션 한다.
3. 메모이제이션 값이 0이 아니라면 해당 크기부터 시작하고, 빈 그리드를 채운다

구현이 이렇게 복잡하지 않을건데 싶어서 다른 아이디어를 떠올림.

아이디어2

1. M x N 행렬을 입력받습니다.

2. 크기 L을 초기값 0으로 설정.

3. 다이나믹 프로그래밍 배열 dp를 생성합니다. dp[i][j]는 (i, j) 위치에서 시작하는 가장 큰 정사각형의 한 변의 길이를 나타낸다.

4. 재귀 함수를 구현합니다. 함수 findLargestSquare(x, y)는 (x, y) 위치에서 시작하는 가장 큰 정사각형의 한 변의 길이를 반환한다:

   • 만약 (x, y) 위치에 장애물이 있다면 0 반환.
   • 그렇지 않으면, 다음과 같이 호출을 통해 가능한 가장 큰 정사각형의 한 변의 길이를 찾는다
     • top = findLargestSquare(x-1, y) # 위쪽 위치에서 시작하는 정사각형의 한 변의 길이
     • left = findLargestSquare(x, y-1) # 왼쪽 위치에서 시작하는 정사각형의 한 변의 길이
     • topLeft = findLargestSquare(x-1, y-1) # 대각선 위 위치에서 시작하는 정사각형의 한 변의 길이
     • dp[x][y] = min(top, left, topLeft) + 1 # 현재 위치에서 시작하는 정사각형의 한 변의 길이를 계산하고 메모이제이션
     • return dp[x][y] # 계산 결과 반환

5. 모든 위치에서 재귀 함수 findLargestSquare를 호출하여 가능한 가장 큰 정사각형의 한 변의 길이를 계산하고, 최대값 L을 업데이트한다.

6. 최대값 L을 출력한다.

코드

M, N = map(int, input().split())
matrix = []
for _ in range(M):
    row = list(map(int, input().split()))
    matrix.append(row)

# 다이나믹 프로그래밍 배열 초기화
dp = [[-1] * N for _ in range(M)]

# 재귀 함수를 사용하여 가장 큰 정사각형의 한 변의 길이를 계산
def solve(x, y):
    if x < 0 or y < 0:
        return 0
    if matrix[x][y] == 0:
        if dp[x][y] == -1:
            top = solve(x-1, y)
            left = solve(x, y-1)
            topLeft = solve(x-1, y-1)
            dp[x][y] = min(top, left, topLeft) + 1
        return dp[x][y]
    return 0

L = 0
for i in range(M):
    for j in range(N):
        if matrix[i][j] == 0:
            L = max(L, solve(i, j))

print(L)

---

회고

아이디어는 금방 생각했는데 구현이 잘 안됐었다. 밖에서 for문을 돌면서 해당 지점부터 크기를 저장하는 방식을 사용하였다.