[백준] 1915번 가장 큰 정사각형

🔔 문제

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

🎯 풀이방법

1. 길이가 2 이상인 정사각형을 확인한다.
   1-1. 현재 자신이 1인가?
   1-2. 왼쪽(←), 위(↑), 대각선(↖) 모두 1인가?
   1-3. 1과 2 모두 해당되면 최소 원소값+1만큼 길이를 update한다. 만약 현재 최대길이보다 크다면 최대길이도 update한다.

2. 1 과정을 (1,1) ~ (N-1, M-1)만큼 반복한다.

3. 최대길이*최대길이를 출력한다.
   
   

예제 1이 위의 과정을 거치면 다음과 같다.

💡 이 문제를 통해 얻어갈 것

다이내믹 프로그래밍 (DP) 사고방식

👁‍🗨 주의할점

Testcase 중에 모두 '0'으로 구성된 배열이 있다. 그러므로 예외처리를 해두자.

java code

한달 간격을 두고 문제를 풀어 보았다. 1번째 코드보다 2번째코드가 시간은 더 빠르지만 메모리 사용량이 더 많다. 하지만, 코드를 보면 1번째 코드가 check라는 함수를 따로 두었고 길이도 더 짧으니 더 clean한 코드 같다.

1) 메모리 27316KB, 시간 376ms, 코드길이 1336 B

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

public class Main {
	static int N,M;
	static int[][] map, dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 1. 입력
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N+1][M+1];
		dp = new int[N+1][M+1];
		String input;
		for(int i=1; i<=N; i++) {
			input = br.readLine();
			for(int j=1; j<=M; j++)
				dp[i][j] = map[i][j] = input.charAt(j-1)-'0';
		}
		
		int max_length = 0;
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=M; j++) {
				if(map[i][j] == 1) {
					dp[i][j] = check(i,j);
					if(max_length <= dp[i][j])
						max_length = dp[i][j];
				}
			}
		}
		
		System.out.println(max_length*max_length);
	}

	static int check(int y, int x) {
		// 좌 위 대각선, 좌, 위
		int check = dp[y-1][x-1];
		int check2 = dp[y][x-1];
		int check3 = dp[y-1][x];
		
		// 하나라도 0이면 크기 1짜리 정사각형
		if(check==0 || check2==0 || check3 == 0)
			return 1;
		
		// 3개 중에 정사각형이 존재하면 그 최솟값보다 1 큰 정사각형
		return Math.min(Math.min(check, check2), check3) + 1;
	}
}

2) 메모리 23676 KB, 시간 352ms, 코드길이 1534 B

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

public class Main {
	static int N,M;
	static int[][] board;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		board = new int[N][M];
		
		boolean isAllZero = false;
		for(int i=0; i<N; i++) {
			String s = br.readLine();
			for(int j=0; j<M; j++) {
				board[i][j] = s.charAt(j)-'0';
				if(board[i][j] > 0)
					isAllZero = true;
			}
		}
		
		// 정사각형 최대길이 초기화
		int max_length = 1;
		if(!isAllZero) {
			System.out.println(0);
			return;
		}
		
		// (행,열) = (1,1) ~ (N-1, M-1)까지 조회
		for(int i=1; i<N; i++) {
			for(int j=1; j<M; j++) {
				// 현재 값이 1인가?
				if(board[i][j] <= 0)
					continue;
				
				// ← 왼 ↖ 왼대각선 ↑ 위 가 모두 1이면 정사각형
				if(board[i][j-1]>0 && board[i-1][j-1]>0 && board[i-1][j]>0) {
					// 3개 중 최소값+1로 dp 값 증가
					int min_val = Math.min(board[i][j-1], board[i-1][j-1]);
					min_val = Math.min(min_val, board[i-1][j]);
					board[i][j] = min_val + 1;
					
					// 이때, 값>max_length이면 최대길이 update
					if(board[i][j] > max_length) 
						max_length = board[i][j];
				}
			}
		}
		
		// 정사각형 넓이 출력
		System.out.println(max_length*max_length);
	}
}