[백준 14500] 테트로미노

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

14500번: 테트로미노

 

이번 문제는 약한 빡구현 문제입니다.

5개의 도형이 있고 이 도형이 회전/대칭 한 모양에 대해 맵을 전체 순회하면서

해당 도형과 일치하는 부분의 합이 가장 큰 값을 구하는 문제입니다.

 

1*4 사각형과 2*2 사각형은 길이가 4, 2이기  때문에 따로 처리하고

나머지 3 도형은 3*3 배열안에 각 도형 모양에 맞게 선언해 주었습니다.

그리고 전체 맵의 길이를 상하좌우 +2만큼 증가시켜 위 3*3 배열에 전체 맵을 순회하여 합을 구하도록 구현했습니다.

import java.io.BufferedReader
import java.io.InputStreamReader

var firstTetromino = arrayOf<Array<Int>>(
    arrayOf(1, 0, 0),
    arrayOf(1, 0, 0),
    arrayOf(1, 1, 0)
)

var firstMirrorTetromino = arrayOf<Array<Int>>(
    arrayOf(0, 0, 1),
    arrayOf(0, 0, 1),
    arrayOf(0, 1, 1)
)

var secondTetromino = arrayOf<Array<Int>>(
    arrayOf(1, 0, 0),
    arrayOf(1, 1, 0),
    arrayOf(0, 1, 0)
)

var secondMirrorTetromino = arrayOf<Array<Int>>(
    arrayOf(0, 0, 1),
    arrayOf(0, 1, 1),
    arrayOf(0, 1, 0)
)

var thirdTetromino = arrayOf<Array<Int>>(
    arrayOf(1, 1, 1),
    arrayOf(0, 1, 0),
    arrayOf(0, 0, 0)
)

val tetrominoArray = arrayOf(firstTetromino, firstMirrorTetromino, secondTetromino, secondMirrorTetromino, thirdTetromino)

var maxSum = 0
lateinit var extendedMap: Array<Array<Int>>
var N = 0
var M = 0

fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))
    val input = br.readLine().split(" ")
    N = input[0].toInt()
    M = input[1].toInt()
    extendedMap = Array(4 + N) { Array(4 + M) { 0 } }

    for (i in 0 until N) {
        val numbers = br.readLine().split(" ")
        numbers.forEachIndexed { _index, _num ->
            extendedMap[i + 2][_index + 2] = _num.toInt()
        }
    }

    for (i in 0 until 5) {
        for (j in 0 until 4) {
            rotateTetromino(i)
            getSumByTetromino(i)
        }
    }

    getLongTetrominoSum()
    getSqureTetrominoSun()

    println(maxSum)

}

fun getLongTetrominoSum() {
    //가로로 4개짜리
    for (i in 0 until N + 2) {
        for (j in 0 until M) {
            val sum = extendedMap[i][j] + extendedMap[i][j + 1] + extendedMap[i][j + 2] + extendedMap[i][j + 3]
            maxSum = Math.max(sum, maxSum)
        }
    }

    //세로로 4개짜리
    for (j in 0 until M + 2) {
        for (i in 0 until N) {
            val sum = extendedMap[i][j] + extendedMap[i + 1][j] + extendedMap[i + 2][j] + extendedMap[i + 3][j]
            maxSum = Math.max(sum, maxSum)
        }
    }
}

//정사각형 도형 순회
fun getSqureTetrominoSun() {
    for (i in 0 until N + 1) {
        for (j in 0 until M + 1) {
            val sum =
                extendedMap[i][j] + extendedMap[i][j + 1] + extendedMap[i + 1][j] + extendedMap[i + 1][j + 1]
            maxSum = Math.max(sum, maxSum)
        }
    }
}

/*
* 1. 전체맵을 순회
* 2. 순회하는 지점에서 3*3 tetromino배열을 올려놓아 1인 부분(도형이 그려진 부분과 겹침)의 합을 구한다.
* 3. 가장 큰놈을 maxSum 에 넣는다.
*
* */
fun getSumByTetromino(index: Int) {
    val tetromino = tetrominoArray[index]

    for (i in 0 until N+1) {
        for (j in 0 until M+1) {
            var sum = 0
            for (k in 0 until 3) {
                for (l in 0 until 3) {
                    val mapXPosition = i + k
                    val mapYPosition = j + l
                    if (extendedMap[mapXPosition][mapYPosition] != 0 && tetromino[k][l] != 0) {
                        sum += extendedMap[mapXPosition][mapYPosition]
                    }
                }
            }
            maxSum = Math.max(maxSum, sum)
        }
    }

}

//배열 회전시키기
fun rotateTetromino(index: Int) {
    val tetromino = tetrominoArray[index]

    val newArray = Array(3) { Array(3) { 0 } }
    for (i in 0 until 3) {
        for (j in 0 until 3) {
            newArray[j][2 - i] = tetromino[i][j]
        }
    }

    tetrominoArray[index] = newArray

}