[백준][KOTLIN][14391] 종이 조각

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

14391번: 종이 조각

문제 풀이

1. 처음에는 N, M 중 큰 값을 기준으로 자르면 무조건 최대 값인줄 알고 풀었다. 반례가 있다는 것을 알지 못했는데 아래의 경우 길이를 길게 자른다고 최대가 되지 않는다. (가로 4, 세로 3으로 짤라야 최대 값이 나온다.

2. N, M 의 최대 값이 4이고 가로/세로 반복이므로 2^(N * M) 의 경우의 수를 가진다.

3. 모든 경우에 대해서 완전 탐색을 수행한다. (i : 행, j : 열)

3-1. 방문여부를 확인하는 2차원 visit 배열을 선언한다.

3-2. 가로 방향부터 탐색한다. 다음 탐색 순서는 j + 1 을 탐색한다.

3-3. 탐색하는 열이 M 과 같을 경우 다음 행을 탐색한다. i + 1

3-4. 탐색하는 행이 N 과 같을 경우 모두 탐색을 하였으므로 가로/세로로 잘랐을 경우에 대한 최대값을 구한다.

이때 visit 배열이 true 이면 가로로 자른 경우라고 생각하고 false 인 경우에는 세로로 짜른 경우라고 생각한다.

코드

import java.io.*

private var result = Int.MIN_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val paper = Array(N) {
        IntArray(M) {
            0
        }
    }

    repeat(N) { index ->
        paper[index] = br.readLine().map { it.digitToInt() }.toIntArray()
    }

    val visit = Array(N) {
        BooleanArray(M) {
            false
        }
    }
    dfs(N, M, paper, visit, 0, 0)
    println(result)
}

private fun dfs(N: Int, M: Int, paper: Array<IntArray>, visit: Array<BooleanArray>, i: Int, j: Int) {
    println("i $i, j $j")

    /*visit.forEach { v ->
        v.forEach {  _v ->
            print("$_v ")
        }
        println("")
    }*/

    if (i == N) {
        // 가로 합 구하기...
        var total = 0

        for (k in 0 until N) {
            var sum = 0
            for (l in 0 until M) {
                if (visit[k][l]) {
                    sum = sum * 10 + paper[k][l]
                    //println("sum = $sum")
                } else {
                    total += sum
                    sum = 0
                }
            }
            total += sum
        }

        // 세로 합 구하기...
        for (k in 0 until M) {
            var sum = 0
            for (l in 0 until N) {
                if (!visit[l][k]) {
                    sum = sum * 10 + paper[l][k]
                    //println("sum222 = $sum")
                } else {
                    total += sum
                    sum = 0
                }
            }

            total += sum
        }

        result = Math.max(result, total)
        return
    }

    if (j == M) {
        // 다음 행으로 이동...
        dfs(N, M, paper, visit, i + 1, 0)
        return
    }

    if (!visit[i][j]) {
        visit[i][j] = true
        // 가로 탐색...
        dfs(N, M, paper, visit, i, j + 1)
        visit[i][j] = false
        // 세로 탐색...
        dfs(N, M, paper, visit, i, j + 1)
    }
}