백준 1915 가장큰정사각형

가장큰정사각형 링크: www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

해당 문제는 2차원 배열에서의 DP를 잘 사용하는 문제 였습니다.

 

해당 Map이 주어졌을 때 N과 M의 사이즈를 하나씩 증가시켜서 Map을 만들었습니다.

Map

그리고 memoization을 사용할 맵을 하나더 만들어 주었는데요

해당 문제에서 memoization을 위해 자신의 대각선에 저장된 값을 가져온뒤에 getSize라는 변수에 저장한뒤

for문을 getSize부터 0까지돌면서 position(y,x)의 위치부터 i까지보았을때 0이없다면 break를 걸어주었습니다.

그리고 해당 i값을 memoization배열에 넣어주었는데요

 

Memoi

그림으로 설명드리자면

position(2,3)을 보았을때 자신의 대각선의 값을 가져와서 +1을 해주려고 합니다.

하지만 position(1,3)의 값이 0이기때문에 position(2,3)의 값은 2가 아닌 1이 됩니다.

하지만 그아래 값인 position(3,3)을 보았을때 

memoi

 

해당값은 for문을 자신의 대각선 만큼 돌게 됩니다 for(i= getSize; i>=0; i--)

이때 getSize는 1이되고 결국 for문을 1부터 0까지 돌게 되죠

이때 position(3,3)에서 1을 뺀 값인 position(2,3)과 position(3,2)의 Map 값이 1이기 때문에

memoi(3,3)은 memoi(2,2)+1을해준뒤에 for문은 멈추게 됩니다.

그리고 해당 로직을 다돌고 가장큰값을 가져와 제곱해주면 됩니다.

해당 로직을 구현하면

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

public class 가장큰정사각형 {

	static int[][] arr;
	static int[][] map;
	static int biggestSize = 0;
	static int N, M;// 가로,세로

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

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

		arr = new int[N + 1][M + 1];
		map = new int[N + 1][M + 1];

		for (int n = 1; n <= N; n++) {
			String input = br.readLine();
			for (int m = 1; m <= M; m++) {
				map[n][m] = Integer.parseInt(input.charAt(m - 1) + "");
			}
		}
		for (int y = 1; y <= N; y++) {
			for (int x = 1; x <= M; x++) {
				if (map[y][x] == 1)
					findBiggestSquare(y, x);
			}
		}

		System.out.println(biggestSize * biggestSize);
	}

	private static void findBiggestSquare(int y, int x) {
		// 대각선이 더떤 값을 갖고 있는지 확인
		int preY = y - 1;
		int preX = x - 1;

		int getSize = arr[preY][preX];

		// false라면 정사각형이 아님 true일 경우만 비교함
		for (int i = getSize; i >= 0; i--) {
			if (compRawAndCol(i, y, x)) {
				// 세로에 getSize+1로 업데이트함
				arr[y][x] = i + 1;
				// biggestSize보다 getSize+1이 더클경우 업데이트함
				biggestSize = Math.max(biggestSize, i + 1);
				break;
			}
		}
		if (arr[y][x] == 0) {
			arr[y][x] = 1;
		}
	}

	// 가로 세로를 비교해서 0이 있는지 없는지 확인하는 함수
	private static boolean compRawAndCol(int pGetSize, int pY, int pX) {

		// 가로 확인
		for (int x = pX; x >= pX - pGetSize; x--) {
			if (map[pY][x] == 0) {
				return false;
			}
		}

		// 세로확인
		for (int y = pY; y >= pY - pGetSize; y--) {
			if (map[y][pX] == 0) {
				return false;
			}
		}
		return true;
	}

}

이 됩니다

 

하지만 이것보다 더 간편하게 짜려면 

그냥 좌측 상단의 값과 상단, 좌측 memoi한 값을 가져와 그 세 값들중에 가장 작은 값에 +1해주는 간단한 방법이 있습니다.

이미 이전에 최적화된 값을 찾아 memoi값에 넣어주었기 때문에 위에 로직처럼 for문을 돌릴 필요가 없기 때문입니다.

해당 코드는 직접 여러분들이 짜보시길 바랍니다.^^

 

정답은 아래에

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

public class 가장큰정사각형 {

	static int[][] arr;
	static int[][] map;
	static int biggestSize = 0;
	static int N, M;// 가로,세로

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

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

		arr = new int[N + 1][M + 1];
		map = new int[N + 1][M + 1];

		for (int n = 1; n <= N; n++) {
			String input = br.readLine();
			for (int m = 1; m <= M; m++) {
				map[n][m] = Integer.parseInt(input.charAt(m - 1) + "");
			}
		}
		for (int y = 1; y <= N; y++) {
			for (int x = 1; x <= M; x++) {
				if (map[y][x] == 1)
					findBiggestSquare(y, x);
			}
		}

		System.out.println(biggestSize * biggestSize);
	}

	private static void findBiggestSquare(int y, int x) {
		int getup = arr[y - 1][x];
		int getleft = arr[y][x - 1];
		int getdia = arr[y - 1][x - 1];

		int minimum = Math.min(getup, getleft);
		minimum = Math.min(getdia, minimum);

		arr[y][x] += minimum + 1;

		biggestSize = Math.max(biggestSize, arr[y][x]);
	}
}