[백준/BOJ] 1051번: 숫자 정사각형

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

1051번: 숫자 정사각형

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

해설

3중 for문을 이용하여 문제를 풀어 보았다.

정사각형의 가장 긴 변이 될 수 있는 값은 n, m을 비교했을 때의 작은 값이다. 이를 len이라 하자.먼저 len만큼 반복문을 돌린다. -> for(i in 0 .. len)이제 가로 세로의 반복문을 설정하는데, i의 값을 뺀 만큼 반복을 돌릴 것이다i를 기준으로 가로 세로의 꼭지점들을 보기 위해서이다.이제 array[j][k] == array[j][k+i], array[j][k] == array[j+i][k], array[j][k] == array[j+i][k+i] 조건들을 모두 만족시킨다면i+1만큼이 최종 한 변의 길이가 된다.(반복문을 0에서부터 시작했기 때문에 1을 더해준다.)반복문을 탈출하여 i+1을 제곱한 값을 출력해주면 된다.

소스 코드

import java.util.*

fun main() {
    var st = StringTokenizer(readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val array = Array(n) { CharArray(m) { '.' } }
    for(i in 0 until n) {
        array[i] = readLine()!!.toCharArray()
    }
    val len = if(n > m) m - 1 else n - 1
    var temp = 0
    for(i in 0 .. len) {
        var check = false
        for(j in 0 until n-i) {
            for(k in 0 until m-i) {
                if(array[j][k] == array[j][k+i] && array[j][k] == array[j+i][k] && array[j][k] == array[j + i][k+i]) {
                    temp = i + 1
                    check = true
                    break
                }
            }
            if(check) break
        }
    }
    println(temp * temp)
}