백준 20208 진우의 민트초코우유 Kotlin (백트래킹)

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

20208번: 진우의 민트초코우유

문제

진우는 민트초코우유를 좋아하는 민초단이다. 힘든 일이 있더라도 민트초코우유 하나를 마시면 기운이 펄펄 솟는다고 한다!

민트초코우유를 너무 좋아하는 나머지 진우는 매일 아침 특정 지역들에서 민트초코우유가 배달된다는 N × N 크기의 2차원 민초마을로 이사를 하였다.

진우는 아침에 눈을 뜨면 집에서 민초마을의 지도를 들고 민트초코우유를 찾으러 출발한다. 이때의 초기 체력은 M이다. 여기에서 체력은 진우가 이동할 수 있는 거리를 나타낸다. 진우는 지도상에서 상, 하, 좌, 우로 1칸씩 이동할 수 있으며 이동하면 체력이 1만큼 줄어든다. 진우가 마을을 돌아다니다가 민트초코우유를 마신다면 체력이 H 만큼 증가하며 진우의 체력이 초기체력 이상으로 올라갈 수 있다. 체력이 0이 되는 순간 진우는 이동할 수 없다.

민트초코를 찾으러 돌아다니다가 마을 한복판에서 체력이 0이 되어 집으로 못 돌아가는 상황은 만들어져서는 안된다. 진우가 얼마나 많은 민트초코우유를 마시고 집으로 돌아올 수 있는지 알아보자.

입력

첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다.

두번째 줄부터 N+1번째 줄에 N칸에 걸쳐서 민초마을의 지도가 주어진다. 각 칸은 공백을 두고 주어지며 지도상에서 진우의 집은 1, 민트초코우유는 2로 주어지며 빈 땅은 0으로 주어진다. 진우의 집은 무조건 한 곳이 주어지며 마을에 배달되는 민트초코우유의 총합은 10개를 넘지 않는다.

출력

진우가 집을 나와서 다시 집으로 돌아올 때 까지 마실 수 있는 민트초코우유의 최대 개수를 출력하자.

좌측 상단을 (0, 0)이라고 하자. 진우의 집은 (6, 3)에 위치한다. 진우가 이동하는 위치, 체력을 순서대로 표시하면 아래와 같다.

• (6, 3) 2
• (7, 4) 3
• (4, 4) 3
• (6, 3) 0

알고리즘 분류

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

풀이

간단한 백트래킹 문제다.

우선 주어진 입력에서 시작점 (1)과 민트초코우유(2)의 좌표를 저장한다.

민트초코우유는 최대 10개이므로, 완전탐색이 충분히 가능하다.

시작점에서 첫 번째 민트초코우유로 10개 모두 선택해 보고, 두 번째 민트초코우유로 또 10개 모두 선택해 보고,

만약 현재 체력으로 시작점으로 돌아가지 못한다면 답을 갱신하지도 않고 다음을 초코우유를 찾지도 않는다.

 

 

코드

import kotlin.math.abs
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

lateinit var graph: Array<IntArray>
var answer = 0
var sr = 0
var sc = 0
val milks = ArrayList<Pair<Int,Int>>()

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

    //input
    val(n,m,h) = getIntList()
    graph = Array(n){r ->
        val list = getIntList()
        for(c in list.indices){
            if(list[c] == 1){
                sr = r
                sc = c
            }else if(list[c] == 2){
                milks.add(Pair(r,c))
            }
        }
        list.toIntArray()
    }

    //solve
    backTracking(sr,sc,0, BooleanArray(milks.size),n,m,h)
    //output
    write("$answer")
    close()
}

fun backTracking(r: Int,c: Int, cnt: Int, visited: BooleanArray, n: Int, curHP: Int, h: Int) {
    val goHome = curHP-(Math.abs(sr-r) + Math.abs(sc-c))
    if(goHome>=0){
        answer = answer.coerceAtLeast(cnt)
    }
    for(i in milks.indices){
        if(visited[i]) continue
        val (nr,nc) = milks[i]
        val diff = curHP-(Math.abs(r-nr) + Math.abs(c-nc))
        if(diff < 0) continue
        visited[i] = true
        backTracking(nr,nc, cnt+1, visited, n, diff + h,h)
        visited[i] = false
    }
}