14500번: 테트로미노

문제 출처 : https://www.acmicpc.net/problem/14500

 

언어 : Kotlin

 

문제 설명 :

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
• 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

 

입력 :

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

 

출력 :

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
5 5 1 2 3 4 5 5 4 3 2 1 2 3 4 5 6 6 5 4 3 2 1 2 1 2 1	19
4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5	20
4 10 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2 1	7

 

풀이 : 

dfs와 dfs로 풀리지 않는 도형을 따로 계산해주는 과정이 필요하다.

dfs로 되는 도형과 안되는 도형은 다음과 같다.

 

ㅜ 모양의 경우 dfs로는 풀리지 않고, 나머지 도형은 dfs 깊이 4로 처리 가능하다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.max

lateinit var map: Array<MutableList<Int>>
lateinit var visited: Array<BooleanArray>
val dx = intArrayOf(0, 1, 0, -1)
val dy = intArrayOf(1, 0, -1, 0)
val xy = IntArray(2)
var result = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (x, y) = readLine().split(" ").map { it.toInt() }
    xy[0] = x.also { xy[1] = y }
    map = Array(x) { mutableListOf() }
    visited = Array(x) { BooleanArray(y) }

    repeat(x) { idx ->
        readLine().split(" ").map { it.toInt() }.also {
            map[idx].addAll(it)
        }
    }

    repeat(x) { a ->
        repeat(y) { b ->
            visited[a][b] = true
            dfs(a, b, 1, map[a][b])
            visited[a][b] = false
            restOfShapes(a, b)
        }
    }

    bw.write("$result")
    bw.flush()
    bw.close()
}

fun dfs(x: Int, y: Int, depth: Int, sum: Int) {
    if (depth == 4) {
        result = max(result, sum)
        return
    }

    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx in 0 until xy[0] && ny in 0 until xy[1] && !visited[nx][ny]) {
            visited[nx][ny] = true
            dfs(nx, ny, depth + 1, sum + map[nx][ny])
            visited[nx][ny] = false
        }
    }
}

fun restOfShapes(x: Int, y: Int) {
    if (y - 1 in 0 until xy[1] && y + 1 in 0 until xy[1]) {
        val value = map[x][y] + map[x][y - 1] + map[x][y + 1]
        if (x + 1 in 0 until xy[0]) result = max(result, value + map[x + 1][y])
        if (x - 1 in 0 until xy[0]) result = max(result, value + map[x - 1][y])
    }

    if (x - 1 in 0 until xy[0] && x + 1 in 0 until xy[0]) {
        val value = map[x][y] + map[x - 1][y] + map[x + 1][y]
        if (y - 1 in 0 until xy[1]) result = max(result, value + map[x][y - 1])
        if (y + 1 in 0 until xy[1]) result = max(result, value + map[x][y + 1])
    }
}