목장 건설하기

문제

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

풀이

• 정사각형의 기준 지점을 맨 오른쪽 아래 칸으로 생각한다.
• 정사각형이 성립하려면 자신의 위, 아래, 대각선을 포함하는 범위내에 장애물이 없어야 한다.
• $dp(r,c)$는 좌표 $(r,c)$까지의 가장 큰 정사각형으로 정의할 수 있다.
• 위 조건들에 따라 $dp(r,c)=min(dp(r-1,c-1),min(dp(r-1,c),dp(r,c-1))$ 로 점화식을 정의할 수 있다.
• 맨 첫 행도 처리해주기 위하여 메모이제이션에 쓰이는 배열의 크기를 $(M+1)\times(N+1)$로 설정해준다.
• 점화식에 따라 로직을 구성하고 최댓값을 계속 갱신하여 답을 도출한다.

로직의 시간복잡도는 $O(MN)$ 형태로 수렴하고 이는 $M=N=1000$인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

import static java.lang.Integer.parseInt;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int M = parseInt(st.nextToken());
    int N = parseInt(st.nextToken());

    int[][] ground = new int[M + 1][N + 1];
    int[][] dp = new int[M + 1][N + 1];

    for (int r = 1; r <= M; r++) {
      st = new StringTokenizer(br.readLine());
      for (int c = 1; c <= N; c++) {
        ground[r][c] = parseInt(st.nextToken());
      }
    }

    int maxValue = 0;

    for (int r = 1; r <= M; r++) {
      for (int c = 1; c <= N; c++) {

        if (ground[r][c] != 0) {
          continue;
        }

        dp[r][c] = Math.min(dp[r - 1][c - 1], Math.min(dp[r - 1][c], dp[r][c - 1])) + 1;
        maxValue = Math.max(maxValue, dp[r][c]);
      }
    }

    System.out.println(maxValue);
    br.close();
  }
}

결과