백준 18290) NM과 K(1)

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개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.

 

 

---

 

출처

코드 플러스: [코딩 테스트 준비 - 기초] 강의

https://code.plus/course/51

 

 

접근 방법

 

백준에 있는 N과 M 시리즈를 응용한 문제라고 볼 수 있다.

 

문제의 키 포인트를 살펴보면

 

 

k개를 선택하되 인접한 칸과는 선택할 수 없다는 것이다.

 

 

 

하지만 나는 이 문장을 보고 "인접한 칸은 안되니 대각선 칸을 선택하면 되겠구나!" 라는 멍청미를 더했다.

(0,0) 에서 (1,1) 로 갈 수 있을 뿐만 아니라

(0,0) 에서 (0,2) 로도 칸을 지정할 수 있기 때문이다.

 

그렇다면 올바른 재귀 탐색은 어떻게 이룰 수 있을까?

 

 

step1.

 

fun go(idx: Int, sum: Int) {
...

for(i in 0 until n) {
        for(j in 0 until m) {
            if(c[i][j]) continue
            
            ...
            
}

 

재귀 함수의 일부분이다.

만약 재귀를 돌 때마다 i=0, j=0 부터 시작하면 어떻게 되는가?

 

(1,2) -> (2,1) -> (3,4) 의 결과를 구하게 된다면

(2,1) 에서 (1,2) -> (3,4) 로 중복된 결과를 구하게 된다.

 

 

 

step2.

 

fun go(idx: Int, sx: Int, sum: Int) {
...

for(i in sx until n) {
        for(j in 0 until m) {
            if(c[i][j]) continue
            
            ...
            
            go(idx+1, i, sum + g[i][j])
            
}

 

for문을 시작할 때 i의 값을 인자로 넘겨주어 오름차순으로 칸을 탐색할 수 있게 됐다.

즉, (1,2) -> (2,1) -> (3,4) 에서 (2,1) -> (1,2) -> (3,4) 로 되돌아가는 것을 방지한다.

 

그런데 만약 (1,2) -> (1,5) -> (3,4) 라면 어떻게 될까?

(1,5) -> (1,2) -> (3,4) 로 탐색할 수 있으므로 이 또한 중복을 야기한다.

 

위의 코드를 통해 행의 중복은 피했지만 열의 중복을 피하지 못했다.

 

 

 

step3.

 

fun go(idx: Int, sx:Int, sy: Int, sum: Int) {
	...
    
	for(i in sx until n) {
        for(j in (if(i==sx) sy else 0) until m) {
            if(c[i][j]) continue
            
            ...
            
            go(idx+1,i,j,sum + g[i][j])

 

(if(i==sx) sy else 0)

 

만약 이전 행과 현재 바라볼 행이 같다면 이전 열에 이어서 탐색하고,

만약 이전 행과 현재 바라볼 행이 같지 않다면 0부터 시작하겠다는 코드이다.

 

 

즉, (1,2) -> (1,5) -> (3,4) 에서 (1,5) 가 시작점이 될 때 (1,2) 와는 행이 같으므로 (1,2)를 제외하고 탐색하게 된다.

 

 

step2, step3 에서 중복을 피하는 과정을 '백 트래킹'이라고도 한다.

 

소스 코드

 

var ans = Int.MIN_VALUE
var n = 0
var m = 0
var k = 0
lateinit var g: Array<List<Int>>
lateinit var c: Array<BooleanArray>
val dx = intArrayOf(-1,1,0,0)
val dy = intArrayOf(0,0,-1,1)

fun main() = with(System.`in`.bufferedReader()) {
    val s = readLine().split(" ").map { it.toInt() }
    n = s[0]
    m = s[1]
    k = s[2]

    g = Array(n) {readLine().split(" ").map { it.toInt() }}
    c = Array(n) {BooleanArray(m)}

    go(0,0,0,0)
    println(ans)
}

private fun go(idx: Int, sx:Int, sy: Int, sum: Int) {
    if(idx==k) {
        if(ans < sum) ans = sum
        return
    }

    for(i in sx until n) {
        for(j in (if(i==sx) sy else 0) until m) {
            if(c[i][j]) continue

            var ok = true
            for(l in 0..3) {
                val nx = i + dx[l]
                val ny = j + dy[l]

                if(nx !in 0 until n || ny !in 0 until m) continue
                if(c[nx][ny]) ok = false
            }

            if(ok) {
                c[i][j] = true
                go(idx+1, i,j, sum + g[i][j])
                c[i][j] = false
            }
        }
    }
}