[Java] 백준 14925번 - 목장 건설하기

• 문제
  • 링크 : https://www.acmicpc.net/problem/14925
  • 땅을 지을 수 있는 가장 큰 정사각형 목장의 한 변의 크기 L 출력하기

 

• 조건
  • 땅에 나무와 돌이 있으면 농장을 지을 수 없음
  • 땅에 정사각형의 목장을 지을 때 가장 큰 목장 짓기

 

• 입력
  • 첫번째 줄
    • 땅의 세로 M, 땅의 가로 N
    • 1 ≤ M ≤ 1000
    • 1 ≤ N ≤ 1000
  • 나머지
    • M x N 크기의 행렬
    • 행렬의 원소 0 : 들판
    • 행렬의 원소 1 : 나무
    • 행렬의 원소 2 : 돌

 

• 출력
  • L 출력하기

 

• 찾아낸 규칙
  • 행렬을 순회하면서 정사각형을 DP형태로 구하기

 

• 로직 1)

import java.io.*;
import java.util.*;

// 목장 건설하기
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] xy = br.readLine().split(" ");
        int y = Integer.parseInt(xy[0]); // 세로 M
        int x = Integer.parseInt(xy[1]); // 가로 N

        // 행렬 생성하기
        int[][] arr = new int[y][x];
        for(int i=0; i<y; i++) {
            String[] s = br.readLine().split(" ");
            for(int j=0; j<x; j++) {
                arr[i][j] = Integer.parseInt(s[j]);
            }
        }

        // 농장을 지을 수 있는 들판(0)일 때 dp를 이용해서 확인
        // 2x2를 점점 확장
        int answer = 0; // 정사각형의 한 변 L
        int[][] dp = new int[y+1][x+1];
        for(int i = 1; i <= y; i++){
            for(int j = 1; j <= x; j++){
                if(arr[i-1][j-1] == 0){
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    answer = Math.max(answer, dp[i][j]);
                }
            }
        }

        System.out.print(answer);
    }
}

 

• 결과
  • 성공
  • 참고 사이트
    • https://velog.io/@pss407/%EB%B0%B1%EC%A4%8014925-%EB%AA%A9%EC%9E%A5-%EA%B1%B4%EC%84%A4%ED%95%98%EA%B8%B0

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