백준 18430 무기 공학 Kotlin (백트래킹)

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

18430번: 무기 공학

문제

공학자 길동이는 외부의 침략으로부터 마을을 지킬 수 있는 부메랑 무기를 개발하는 공학자다. 길동이는 부메랑 제작을 위한 고급 나무 재료를 구했다. 이 나무 재료는 NxM크기의 직사각형 형태이며 나무 재료의 부위마다 그 강도가 조금씩 다르다.

예를 들어 나무 재료의 크기가 2x3일 때는 다음과 같이 총 6칸으로 구성된다.

길동이는 이처럼 넓은 사각형 형태의 나무 재료를 잘라서 여러 개의 부메랑을 만들고자 한다. 그리고 부메랑은 항상 3칸을 차지하는 ‘ㄱ’모양으로 만들어야 한다. 따라서 부메랑의 가능한 모양은 다음과 같이 총 4가지다.

이때 부메랑의 중심이 되는 칸은 강도의 영향을 2배로 받는다. 위 그림에서 노란색으로 칠한 부분이 ‘중심이 되는 칸’이다. 예를 들어 앞선 예시에서는 다음과 같이 2개의 부메랑을 만들 수 있으며, 이때 만들어지는 부메랑들의 강도의 합은 46으로 이보다 강도의 합이 높아지는 경우는 없다.

또한 나무 재료의 특정 위치는 아예 사용하지 않아도 괜찮다. 예를 들어 앞선 예시에서 다음과 같이 1개의 부메랑만을 만들어도 괜찮다. 다만, 이렇게 만들게 되면 부메랑들의 강도의 합이 18이 되기 때문에 비효율적이다.

나무 재료의 형태와 각 칸의 강도가 주어졌을 때, 길동이가 만들 수 있는 부메랑들의 강도 합의 최댓값을 출력하는 프로그램을 작성하시오. 

입력

첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내는 M개의 자연수 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ K ≤ 100)

출력

첫째 줄에 길동이가 만들 수 있는 부메랑들의 강도 합의 최댓값을 출력한다.

단, 나무 재료의 크기가 작아서 부메랑을 하나도 만들 수 없는 경우는 0을 출력한다.

알고리즘 분류

• 백트래킹

풀이

백트래킹 문제이다!

우선 2차원 그래프를 1차원 인덱스로 바꾼다.

4행 5열 그래프라면 인덱스 0부터 19까지 탐색하게 되는데,

이를 다시 2차원으로 바꾸려면 

r = idx/m

c = idx%m

을 해주면 된다.

 

dfs에서 0 <= idx < n*m에 해당하는 모든 좌표를 탐색하며, 현재 좌표에서 4개 모양의 부메랑을 만들 수 있는지 확인한다.

현재 dfs의 깊이를 0이라고 하자.

만약 부메랑을 만들 수 있다면 만들어진 부메랑의 강도 합을 더한 값, 다음 좌표와 함께(curIdx+1) 다음 dfs를 호출한다.

그럼 이제 dfs의 깊이는 1이고, 이전 위치에 부메랑을 설치하고 넘어온 dfs이며, 위의 과정을 반복한다.

 

전체적인 풀이는 다음과 같다.

1. 2차원 그래프를 1차원 인덱스를 이용해 0부터 n*m미만까지 탐색한다.

2. 현재 인덱스에 부메랑의 4개 모양중 하나라도 만들 수 있다면 만들고 다음 인덱스로 넘어간다.

3. 만약 현재 인덱스에 만들 수 있는 부메랑이 없다면 바로 다음 인덱스를 탐색한다.

4. 위에서 부메랑을 만들 수 있는 이전 인덱스에 만들고 다음 인덱스로 넘어갔는데,
   이전 인덱스에 부메랑을 안 만들고 넘어가는 경우가 더 부메랑의 강도 합이 높을 수 있으니,
   다음 dfs를 호출한 뒤에는 다시 부메랑을 없애주어, 부메랑을 만들지 않고 넘어가는 경우도 구현해준다. 

코드

val br = System.`in`.bufferedReader()
//1<=n,m<=5
lateinit var graph : Array<IntArray>
lateinit var visited : Array<BooleanArray>
var answer =0

fun shapeSum(shape : Int, r : Int, c: Int, n : Int, m : Int, type : Int) : Int{
    return when(type){
        //생성
        0->{
            when(shape){
                0 ->{
                    if(r+1 !in 0 until n
                        || c+1 !in 0 until m
                        || visited[r][c]
                        ||visited[r+1][c]
                        ||visited[r][c+1])
                        0
                    else{
                        visited[r][c] = true
                        visited[r+1][c] = true
                        visited[r][c+1] = true
                        graph[r][c]*2+graph[r+1][c]+graph[r][c+1]
                    }
                }
                1->{
                    if(r-1 !in 0 until n
                        || c+1 !in 0 until m
                        || visited[r][c]
                        || visited[r-1][c]
                        || visited[r][c+1]
                    ){
                        0
                    }
                    else{
                        visited[r][c] = true
                        visited[r-1][c] = true
                        visited[r][c+1] = true
                        graph[r][c]*2+graph[r-1][c]+graph[r][c+1]
                    }
                }
                2->{
                    if(r-1 !in 0 until n
                        || c-1 !in 0 until m
                        || visited[r][c]
                        || visited[r-1][c]
                        || visited[r][c-1]
                    ){
                        0
                    }
                    else{
                        visited[r][c] = true
                        visited[r-1][c] = true
                        visited[r][c-1] = true
                        graph[r][c]*2+graph[r-1][c]+graph[r][c-1]
                    }
                }
                else->{
                    if(r+1 !in 0 until n
                        || c-1 !in 0 until m
                        || visited[r][c]
                        || visited[r+1][c]
                        || visited[r][c-1]
                    ){
                        0
                    }
                    else{
                        visited[r][c] = true
                        visited[r+1][c] = true
                        visited[r][c-1] = true
                        graph[r][c]*2+graph[r+1][c]+graph[r][c-1]
                    }
                }
            }
        }
        //삭제
        else->{
            when(shape){
                0 -> {
                    visited[r][c] = false
                    visited[r + 1][c] = false
                    visited[r][c + 1] = false
                    0
                }
                1-> {
                    visited[r][c] = false
                    visited[r - 1][c] = false
                    visited[r][c + 1] = false
                    0
                }
                2-> {
                    visited[r][c] = false
                    visited[r - 1][c] = false
                    visited[r][c - 1] = false
                    0
                }
                else->{
                    visited[r][c] = false
                    visited[r + 1][c] = false
                    visited[r][c - 1] = false
                    0
                }
            }
        }

    }

}

fun dfs(curIdx : Int, n : Int, m : Int, sum : Int){
    var cur = curIdx
    answer = answer.coerceAtLeast(sum)
    while(cur<n*m) {
        var r = cur/m
        var c = cur%m
        for (i in 0 until 4) {
            //생성
            val next = shapeSum(i, r, c,n, m,0)
            if(next==0) continue

            dfs(cur+1, n, m, sum+next)
            //삭제
            shapeSum(i,r,c,n,m,1)
        }
        cur++
    }
}

fun main() = with(System.out.bufferedWriter()){
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    graph = Array(n){br.readLine().split(' ').map{it.toInt()}.toIntArray()}
    visited = Array(n){BooleanArray(m)}
    dfs(0,n,m,0)
    write("$answer")
    close()
}