💡[BOJ 1915/ 코틀린] 가장 큰 정사각형 - DP

백준 1915_가장 큰 정사각형 | 문제 링크

대표적인 동적계획법/동적 프로그래밍 (DP:Dynamic Programming) 문제입니다.

 

문제 설명

n*m 크기의 0과 1로만 이루어진 이차원 배열이 주어집니다.

이 배열에서 (테두리, 내부 포함) 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제입니다.

 

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

입력예

 

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

출력예

 

전체 코드

fun main() {
	var n = 0
	var m = 0
	var maxLen = 0
	readLine()!!.split(" ").let {
		n = it[0].toInt()
		m = it[1].toInt()
	}
	val map = Array(n) { Array(m) {0} }
	map.forEachIndexed { i, row ->
		val tmp = readLine()
		row.forEachIndexed { j, _ ->
			map[i][j] = tmp!![j].digitToInt()
		}
	}
	if (n > 1 && m > 1) {
		for (i in 1 until n) {
			for (j in 1 until m) {
				if (map[i][j] != 0) {
					map[i][j] = min(map[i - 1][j], map[i][j - 1], map[i - 1][j - 1]) + 1
				}
			}
		}
	}
	map.forEach { it.forEach { i -> maxLen = Math.max(maxLen, i) } }
	println(maxLen * maxLen)
}

fun min(a:Int, b:Int, c:Int):Int = if (a > b) { if (b > c) c else b	} else { if (a > c) c else a }

옛날에 정사각형이 아닌 직사각형의 경우를 풀어봤어서, 대충 아이디어를 바로 떠올릴 수 있었습니다.

먼저 말씀드리자면, 배열의 각 지점에 쓰여진 정수(현재는 0, 1)는 해당 지점까지 만들 수 있는 정사각형의 한 변의 길이입니다.

 

예를 들어 다음과 같은 배열(이하 map)이 주어졌을 때를 살펴보겠습니다.

배열 예시

 

map에서 0행, 0열을 제외한 모든 점을 조사합니다.

해당 지점(이하 조사점)을 우측하단으로 하는 2*2 크기의 정사각형을 살펴봅니다.

첫번째 탐색

먼저, 조사점이 0인 경우는 (당연히) 정사각형을 만들 수 없습니다.

조사점이 1인 경우, 조사점의 좌측, 좌상단, 상단 지점의 최소값을 조사합니다.

그 최소값에 1을 더한 값을 조사점에 대입합니다.

 

다시 말씀드리자면, 배열의 각 지점에 쓰여진 정수(현재는 0, 1)는 해당 지점까지 만들 수 있는 최대 정사각형의 한 변의 길이입니다.

조사점의 좌측, 좌상단, 그리고 상단까지 만들 수 있는 최대 정사각형의 한 변의 길이는 0이므로, 조사점까지 한 점을 더 이어 0 + 1의 만들 수 있습니다.

 

같은 로직으로 (1,2), (1,3), (2,1) 좌표를 확인하면 모두 1이 대입됩니다.

이제 (2,2) 좌표를 확인해보겠습니다.

DP - Down to Top 과정

(2,2) 조사점에서는 자신을 제외한 나머지 세 지점의 최소값이 1이므로, 조사점에 1+1=2를 대입합니다. 즉, 조사점을 우하단 중심으로 한 변의 길이가 2인 정사각형을 만들 수 있습니다.

 

다음 조사점은 (2,3)이 아닌 (3,1)도 아닌 (3,2)입니다. map[i][j]가 0인 지점은 조사하지 않습니다.

 

이 로직을 모두 시행하고 나면 이런 map이 만들어집니다.

결과

이제 다시 map을 완전탐색하여, 가장 큰 정수(최대 정사각형 한 변의 길이)를 제곱하여 출력하면 답입니다.