[Algorithm] 백준 4095번(BOJ 4095) 최대 정사각형 문제풀이!!(Java)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 백준 온라인 저지에 있는 4095번 최대 정사각형 문제를 풀어보겠습니다.

문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다.

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

 

1. 문제 설명

해당 문제는 다이내믹 프로그래밍 유형으로 문제를 풀기 위해서 점화식을 도출해야 합니다.

사실 대부분의 DP문제가 점화식만 도출하면 코드 작성은 간단한데, 이번 문제도 다르지 않습니다.

주어진 2차원 배열의 최대 정사각형의 크기를 map[i][j]로 가정하면 점화식은 다음과 같습니다.

map[i][j] = min(map[i-1][j-1], map[i-1][j], map[i][j-1]) + 1

즉, 2차원 배열의 좌측 대각선, 좌측, 위의 값 중 최솟값에 + 1을 하는 것입니다.

기본적으로 정사각형 성질은 모든 변의 길이가 같다는 것이므로 위와 같은 점화식이 도출됩니다.

그럼 코드를 살펴보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingnojam.algorithm.boj;

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

// 백준온라인저지 4095번 최대 정사각형 문제풀이
public class BOJ_4095 {
	public static void main(String[] args) throws IOException {
		// 입출력을 위한 객체
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// 테스트케이스 만큼 반복
		while (true) {
			// 2차원 배열 행과 열 길이 받기
			String[] NM = br.readLine().split(" ");
			int N = Integer.parseInt(NM[0]);
			int M = Integer.parseInt(NM[1]);
			int[][] map = new int[N][M];

			// 테스트케이스가 끝나면 반복문 빠져나오기
			if (N == 0 && M == 0) {
				break;
			}

			// 주어진 2차원 배열에 1이 있는지 확인을 위한 변수
			boolean oneCount = false;
			// map변수에 값을 채워나가면서 1이 있는지 체크
			for (int i = 0; i < N; i++) {
				String[] mapInfo = br.readLine().split(" ");
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(mapInfo[j]);
					if (map[i][j] == 1) {
						oneCount = true;
					}
				}
			}

			// 1이 있다면 최소 정사각형의 값은 1, 없다면 0
			// 테스트케이스 별로 결과값을 저장하기 위한 변수
			int result = oneCount ? 1 : 0;

			// 2차원 배열 순회하면서 DP를 통해 값 도출
			// DP 점화식 : map[i][j] = map[i-1][j-1], map[i-1][j], map[i][j-1] 셋 중의 최소 값 + 1
			for (int i = 1; i < N; i++) {
				for (int j = 1; j < M; j++) {
					if (map[i][j] == 1) {
						map[i][j] = getMinValue(map[i - 1][j - 1], map[i - 1][j], map[i][j - 1]);
						// 최대 정사각형의 길이를 result변수에 저장
						result = Math.max(result, map[i][j]);
					}
				}
			}
			// 출력을 위해 결과 값 저장
			bw.write(String.valueOf(result));
			bw.newLine();
		}
		// 결과값 출력
		bw.flush();
	}

	/**
	 * 입력받은 3개의 변수 중 최솟값을 반환하는 메서드
	 */
	public static int getMinValue(int a, int b, int c) {
		return Math.min(Math.min(a, b), c);
	}
}

 

작성한 코드의 라인마다 주석을 달아놓았습니다.

주석과 코드를 같이 살펴보시면 이해하는데 크게 어렵지 않으실 겁니다.

감사합니다.

---