백준 18290) NM과 K(1)

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

18290번: NM과 K (1)

 

1. 문제

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

2. 입력

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

3. 출력

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

4. 제한

- 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.

 

      

      

      

    
    

      <kotlin />
    
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.

 

      

      

      

    
    

      <kotlin />
    
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.

 

      

      

      

    
    

      <kotlin />
    
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)를 제외하고 탐색하게 된다.

 

 

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

 

소스 코드

 

      

      

      

    
    

      <kotlin />
    
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
            }
        }
    }
}