[백준 - 14925][GOLD 4][해설 X] - 목장 건설하기(JAVA)

 

문제 링크

---

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

 

문제

---

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

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

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

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

 

입력

---

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

 

출력

---

L

 

해결 코드

---

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

public class Main {
    static int[][] map;
    static int[][] dp;
    static int max;
    static boolean[][] visited;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        map = new int[M+1][N+1];
        dp = new int[M+1][N+1];
        visited = new boolean[M+1][N+1];

        for(int row=1;row<=M;row++){
            st = new StringTokenizer(br.readLine());

            for(int col=1;col<=N;col++){
                map[row][col] = Integer.parseInt(st.nextToken());
            }
        }

        //모든 좌표를 순회하며 해당 좌표를 사용했을 때 만들 수 있는 최대 정사각형의 크기를 구한다.
        for(int row=1;row<=M;row++){
            for(int col=1;col<=N;col++){
                getMax(row,col);
            }
        }

        System.out.println(max);
    }
   
    public static int getMax(int row, int col){
        //이미 아는 크기면 해당 크기 반환
        if(visited[row][col]){
            return dp[row][col];
        }

        visited[row][col] = true;
        
        //들판이 아니면 현재 칸을 사용하지 못한다.
        if(map[row][col]!=0){
            dp[row][col] = 0;
        }
        //열의 시작, 행의 시작 값이면 해당 칸 밖에 사용하지 못한다.
        else if(row == 1 || col == 1){
            dp[row][col] = 1;
        }

        //점화식
        // (행,열)을 사용해서 정사각형을 만들 때의 최대 크기 = min((행-1,열-1)을 사용해서 정사각형을 만들 때의 최대 크기,(행-1,열)을 사용해서 정사각형을 만들 때의 최대 크기,(행,열-1)을 사용해서 정사각형을 만들 때의 최대 크기)+1
        else{
            int available = Math.min(getMax(row-1,col-1),getMax(row,col-1));
            available = Math.min(available,getMax(row-1,col));
            dp[row][col] = available + 1;
        }
        
        //최대크기 저장
        max = Math.max(max,dp[row][col]);

        return dp[row][col];
    }
}

 

 

실행 결과

---

 

팁

---

• 가장 큰 것을 구하기 위해선 가장 작은 것이 무엇인지, 이후 어떻게 커지는지를 파악해야한다. 
• 최대값을 구하는 알고리즘은 DP, BFS, 그리디 등이 있다.