백준 14925 목장 건설하기 (Java)

1. 문제 링크

14925번: 목장 건설하기

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 목장을 건설 가능한 좌표는 true로, 건설 불가능한 좌표는 false로 저장한다.
2. 건설이 가능한 좌표가 나왔으면 해당위치에서 (-1, 0), (-1, -1), (0, -1)의 dp 중 최솟값을 선택하고 1을 더한 값으로 저장한다.
   2-1. 앞의 3 좌표는 정사각형의 각 모서리로 포함되는 위치들에서 나왔다
   2-2. 그 중 제일 작은 값만큼만 건설이 가능하고, 지금 자리도 건설이 되니까 1을 더했다.
3. 좌표마다 dp를 구할 때마다 최댓값을 갱신한다.

 

4. 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] split = br.readLine().split(" ");
		int M = Integer.parseInt(split[0]);
		int N = Integer.parseInt(split[1]);
		boolean[][] map = new boolean[M][N];
		int[][] dp = new int[M+1][N+1];
		for(int i=0;i<M;i++) {
			split = br.readLine().split(" ");
			for(int j=0;j<N;j++) {
				if(split[j].equals("0")) {
					map[i][j] = true; 
				}
				else {
					map[i][j] = false;
				}
			}
		}
		int max = 0;
		for(int i=1;i<M+1;i++) {
			for(int j=1;j<N+1;j++) {
				if(map[i-1][j-1]) {
					dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1])+1;
					max = Math.max(max, dp[i][j]);
				}
			}
		}
		System.out.println(max);
	}
}