[백준 1915] - 가장 큰 정사각형(Kotlin)[골드4]

문제

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

1915번: 가장 큰 정사각형

 

문제 풀이

처음에는 점 하나를 잡고 탐색을 해서 정사각형을 판별하는 문제로 생각했는데, n과 m이 각각 1000이라 모든 점에 대해서 탐색하기가 무리가 있었고, 그 점에 대한 정사각형을 판별하는 과정도 굉장히 문제가 있었다. 

그러다 무작정 그림을 그리다 보니 규칙을 발견할 수 있었다.

 

정사각형이란 모두 1로 이루어져야 하고, 가로와 세로의 길이가 같아야 한다.

하나의 점에서 2x2의 정사각형인지 판단하는 방법은 간단했다.

3가지 방향에 대해서 0이 없어야 한다.

하지만 3x3, 4x4 , ... nxn의 영역의 정사각형을 확장하기가 어려웠다.

영역에 대해서 정사각형으로 만들 수 있는 길이를 계산해 봤다.

각 영역의 값은 만들 수 있는 정사각형의 변의 길이었다.

분명히 우측 하단의 점은 3x3의 정사각형을 만들 수 있다는 것을 논리적으로 알았지만, 식을 세우는 것이 어려웠다.

하지만 각 점에서 정사각형을 만들 수 있는지 화살표를 그려봤고, 규칙을 알 수 있었다.

1이라는 값은 해당 영역이 1x1의 정사각형이라는 뜻이고, 2라면 2x2의 정사각형이라는 값이다.

여기서 주목할 점은 각 점에서 뻗어나가는 화살표의 값이었다.

값이 채워진 부분은 해당 구간이 정사각형이라는 뜻이고, 다음과 같은 변이 보장받았다.

 

(3,3) 좌표에 대해 (2,3), (3,2), (2,2)를 감싸는 정사각형의 변의 길이가 2였고, 3x3의 정사각형을 이루고 있었다.

3 방향의 값에 의해 정사각형의 최대 크기가 정해지는 것이었다.

 

위의 경우처럼 세 방향이 같은 값을 가지고 있다면 값+1인 정사각형이 그려졌지만, 다른 값이 있는 경우도 생각을 해봐야 했다.

 

(1,3)을 0으로 바꿨고, 그 결과로 3*3의 정사각형이 아닌 2*2의 정사각형이 최대라는 것을 알 수 있었다.

3*3으로 확장하지 못한 이유는 (2,3)의 값에 영향이 있었고, 3 방향의 값 중 최솟값에 영향을 받고 있었다.

 

즉 식을 세워보면  graph[i][j] = min(graph[i-1][j-1], graph[i][j-1], graph[i-1][j]) +1 이 되는 것을 알 수 있다.

 

전체 코드

import kotlin.math.*

class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0
    private var m = 0
    private lateinit var graph: Array<IntArray>
    private var answer = 0
    fun run() {
        input()
        solve()
        print(answer * answer)
    }

    private fun input() {
        br.readLine().split(" ").map { it.toInt() }.apply {
            n = this[0]
            m = this[1]
        }
        graph = Array(n) {
            val line = br.readLine()
            IntArray(m) { idx ->
                line[idx].toString().toInt()
            }
        }
    }

    private fun solve() {
        for (i in 0 until n) {
            for (j in 0 until m) {
                if (graph[i][j] == 0) {
                    continue
                }
                if (i - 1 >= 0 && j - 1 >= 0) {
                    graph[i][j] = minOf(graph[i - 1][j - 1], graph[i - 1][j], graph[i][j - 1]) + 1
                }
                answer = max(answer, graph[i][j])
            }
        }
    }
}

fun main() {
    val solution = Solution().run()
}