백준 14391 종이 조각 Kotlin (완전탐색)

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

14391번: 종이 조각

문제

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 비트마스킹

풀이

완전 탐색, 비트마스킹 문제이다.

본인은 dfs를 이용한 완전 탐색으로 풀었다.

풀이는 아래 블로그를 참고했으며. 우선 아래의 풀이를 읽어보고 이해가 되지 않는다면 아래 블로그에 자세한 설명이 있으니 보면 도움이 될 것 같다.

https://retry-again.tistory.com/11

[백준 14391] 종이조각

 

비트마스킹 풀이는 아래 블로그에서 참고!

https://vixxcode.tistory.com/23

14391번 종이조각 백준 파이썬

 

F	T	T
F	T	T
T	T	T
F	F	F

 

위의 표에서 F는 세로, T는 가로로 자른 경우를 의미한다.

예제 3번을 예로 들면

00 + 01 + 10+ 111 +1 + 0 + 0이 된다.

 

그러면 어떻게 이러한 표가 만들어지게끔 할 수 있을까.

 

    check[r][c]=true
    dfs(r,c+1,n,m,graph)
    check[r][c]=false
    dfs(r,c+1,n,m,graph)

핵심 코드이다.

어떠한 칸을 탐색할 때, 해당 칸을 가로로 사용할지, 세로로 사용할지만 고려하면 된다.

첫 번째 dfs는 check[r][c] =true로 현재 칸을 가로로 사용하고 다음 칸을 탐색하고,

두 번째 dfs는 check[r][c] =false로 현재 칸을 세로로 사용하고 다음 칸을 탐색한다.

이 코드로 가로, 세로로 찢는 모든 경우를 탐색할 수 있고,

열이 그래프를 벗어나면 다음 행의 0열로 탐색을 이어가고,

행이 그래프를 벗어나면 만들어진 표의 합을 구한 후 최댓값을 갱신한다.

 

코드1(완전 탐색)

import kotlin.math.*
var answer=0
val check = Array<BooleanArray>(4){ BooleanArray(4) }

fun sum(n : Int, m : Int, graph : Array<String>) : Int{
    var total =0
    for(r in 0 until n){
        var sum=0
        for(c in 0 until m){
            //가로 연속
            if(check[r][c]){
                sum= sum*10 + Character.getNumericValue(graph[r][c])
            }
            //끊기면 전체 합에 추가
            else{
                total+=sum
                sum=0
            }
        }
        total+=sum
    }
    for(c in 0 until m){
        var sum=0
        for(r in 0 until n){
            //세로 연속
            if(!check[r][c]){
                sum = sum*10 + Character.getNumericValue(graph[r][c])
            }
            //끊기면 전체 합에 추가
            else{
                total+=sum
                sum=0
            }
        }
        total+=sum
    }
    return total
}

fun dfs(r : Int, c : Int, n : Int, m : Int, graph: Array<String>){

    if(r==n){
        answer = max(answer,sum(n,m,graph))
        return
    }
    if(c==m){
        dfs(r+1,0, n, m, graph)
        return
    }
    check[r][c]=true
    dfs(r,c+1,n,m,graph)
    check[r][c]=false
    dfs(r,c+1,n,m,graph)
}


fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val graph = Array<String>(n){
        val str = br.readLine()
        str
    }
    dfs(0,0,n,m,graph)
    write("$answer")
    close()
}

코드2(비트마스킹)

val br = System.`in`.bufferedReader()

lateinit var graph: Array<IntArray>

fun main() = with(System.out.bufferedWriter()){

    //input
    val (n,m) =br.readLine().split(' ').map{it.toInt()}
    graph= Array(n){
        val line = br.readLine()
        IntArray(m){Character.getNumericValue(line[it])}
    }

    //solve
    //0부터 1111~
    //0이면 가로 1이면 세로
    var answer=0
    for(state in 0 until (1 shl n*m)){
        var sum=0
        //가로
        for(r in 0 until n){
            var cur=0
            for(c in 0 until m){
                if(state and (1 shl r*m+c) ==0){
                    cur = cur*10 + graph[r][c]
                }
                else{
                    sum+=cur
                    cur=0
                }
            }
            sum+=cur
        }
        //세로
        for(c in 0 until m){
            var cur=0
            for(r in 0 until n){
                if(state and (1 shl r*m+c) !=0){
                    cur = cur*10 + graph[r][c]
                }
                else{
                    sum+=cur
                    cur=0
                }
            }
            sum+=cur
        }
        answer = answer.coerceAtLeast(sum)
    }

    write("$answer")

    close()
}