백준 18290 NM과 K (1) Kotlin (백트래킹)

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

18290번: NM과 K (1)

문제

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.

입력

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.

출력

선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.

제한

• 1 ≤ N, M ≤ 10
• 1 ≤ K ≤ min(4, N×M)
• 격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
• 항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

2차원 그래프 백트래킹 문제이다.

모든 좌표에 대해 선택하기, 선택 안 하기 두 가지 선택지를 모두 선택해보는 것으로 풀 수 있다.

풀이에서 사용한 간단한 트릭은 2차원 좌표를 1차원 인덱스로 두는 것이다.

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

1. 0번 인덱스부터 탐색을 시작한다.

2. 0번 인덱스를 2차원 좌표로 변환한다. (idx/m,idx%m)

3. 해당 좌표에서 인접 4방향에 이미 방문을 했는지 체크한다.

4. 인접 4방향에 방문을 하지 않았다면 조건에 부합하니 해당 좌표는 체크하고 다음(재귀의 다음 뎁스)으로 넘어간다. 이때 sum을 누적, 체크 count를 증가시킨다.

5. 인접 4방향을 방문했든, 방문하지 않았든 해당 좌표를 체크하지 않은 상태로 다음으로 넘어간다.

6. k개의 좌표를 모두 체크했다면 정답을 갱신하고 재귀를 종료시킨다.

7. 인덱스가 n*m일 때도 모든 그래프를 탐색했다는 의미로 재귀를 종료시킨다. 이때 위 6번 로직보다 다음에 와야 한다. 앞에 온다면 그래프의 맨 끝 좌표를 체크하고 넘어간 순간을 기록할 수 없다.

4,5,6 과정이 핵심이고 2는 팁이다.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()
lateinit var graph: Array<List<Int>>
var answer = -Int.MAX_VALUE
val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(1, 0),
    arrayOf(0, -1),
    arrayOf(-1, 0)
)

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, m, k) = getIntList()
    graph = Array(n) { getIntList() }
    //solve
    backTracking(0, 0, 0, Array(n) { BooleanArray(m) }, n, m, k)
    //output
    write("$answer")
    close()
}

fun backTracking(idx: Int, cnt: Int, sum: Int, visited: Array<BooleanArray>, n: Int, m: Int, k: Int) {
    if (cnt == k) {
        answer = answer.coerceAtLeast(sum)
        return
    }
    if (idx == n * m) return
    val r = idx / m
    val c = idx % m
    if (checkCanMove(r, c, n, m, visited)) {
        visited[r][c] = true
        backTracking(idx + 1, cnt + 1, sum + graph[r][c], visited, n, m, k)
        visited[r][c] = false
    }
    backTracking(idx+1,cnt,sum,visited,n,m,k)
}

fun checkCanMove(r: Int, c: Int, n: Int, m: Int, visited: Array<BooleanArray>): Boolean {
    for (i in 0 until 4) {
        val nr = r + dir[i][0]
        val nc = c + dir[i][1]
        if(nr !in 0 until n) continue
        if(nc !in 0 until m) continue
        if(visited[nr][nc]) return false
    }
    return true
}