[백준/BaekJoon] 숫자 정사각형 (kotlin/코틀린)

1. 문제 설명

 

 

문제

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

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

 

 

2. 알고리즘 설명

 

일단 머리속으로 생각한 알고리즘은  1×1 , 2×2 , 3×3 일 때의 꼭지점의 값을 비교해서 같으면 answer 변수에 담긴 값이랑 비교해서 더 큰값을 저장하게 했습니다.

 

코드로 보여드리겠습니다.

 

package kr.co.composeex

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.max
import java.util.*

var answer = 0

fun main(args : Array<String>) {

 val bf = BufferedReader(InputStreamReader(System.`in`))

 val st = StringTokenizer(bf.readLine())

 val N = st.nextToken().toInt()

 val M = st.nextToken().toInt()

 val map = Array<Array<Int>>(N){Array<Int>(M){ 0 } }

 for(i in 0 until N) {

     val row = bf.readLine()

     for(j in 0 until M) {
        map[i][j] = row[j].toString().toInt()
     }
 }

 var plusValue = 0

 while(plusValue < N) {

     for( i in 0 until N) {

         for(j in 0 until M) {

             if(i+plusValue>0&&i+plusValue<N&&j+plusValue>0&&j+plusValue<M) {

                 if(map[i][j] == map[i+plusValue][j] && map[i+plusValue][j] == map[i+plusValue][j+plusValue] && map[i+plusValue][j+plusValue] == map[i][j+plusValue]) {
                     answer = max(answer,plusValue)
                 }

             }

         }

     }
     plusValue++

 }
  print((answer + 1) * (answer+1))

}

 

plusValue 변수는 현재 1×1 , 2×2 , 3×3 인지 체크하는 변수입니다.

이중 for문으로 map을 돌면서 해당 칸에서 1×1 , 2×2 , 3×3... 이 map안에 존재하는지 그리고 꼭지점의값을 비교합니다.

4개의 꼭지점의 값을 다 비교할 필요없이 a,b,c,d 가 있다면 a=b , b=c , c=d 라면 a=d가 성립하는걸로 조건은 3개만 넣었습니다.

 

결과는....

 

그래도 혹시나 이중for문에 while문이 있어서 시간초과가 뜨지 않을가 걱정했는데 상당히 빠르게 통과한거 같습니다.