[ 알고리즘 / Kotlin ] 백준 15686 치킨 배달

안녕하세요 gyub(귭)입니다 ㅎㅎㅎ
https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

치킨 배달 문제입니다!! 브루트 포스 문제이져ㅎ

전 백트래킹을 사용했습니다

 

문제를 간단하게 요약하면 이렇습니다.

 

주어진 치킨 집들 중 m개의 치킨 집과 모든 집의 거리의 최솟값을 구하는 문제입니다.

문제 내용 자체가 그리 어렵지 않으니 이렇게만 요약하고 넘어가겠습니다 (^~^)

 

접근 방법

치킨 집들 중 중복 없이 m개를 뽑은 후 각 집들과의 거리를 계산한 후 tmp변수에 넣어주고

최종적으로 tmp의 최솟값을 answer 변수에 넣어주며 마무리

 

코드

변수, 배열을 선언한게 꽤 돼서 설명부터 드리겠습니다!!!

 

private const val HOME = 1 // 1 일때 집
private const val CHICKEN = 2 // 2 일때 집

private lateinit var chicken: ArrayList<Pair<Int, Int>> // 치킨집의 좌표 저장 배열
private lateinit var home: ArrayList<Pair<Int, Int>>  // 집의 좌표 저장 배열
private lateinit var visit: BooleanArray // backtracking을 위한 방문 배열
private lateinit var comPareAnswer: Array<Pair<Int, Int>> // 치킨집들 중 뽑은 m개 저장 배열
private var n = 0  
private var m = 0
private var tmpAnswer = 0 // 최솟값을 비교하기 위한 tmp 변수
private var answer = Int.MAX_VALUE // 최종 답

주석으로 처리해봤는데 어느정도 이해가 가시나요?? 안 가시면 밑에 코드 보시면 이해가 가실겁니다 핳;

 

일단 이 문제는 입력으로 주어지는 배열을 다 저장할 필요가 없습니다!!!

왜냐, 우리는 치킨 집과 집 사이의 '치킨 거리'만 구하면 되니까유 

그리고 '치킨 거리'의 공식이 나와있으므로 더더욱 빈 공간은 필요가 없게 됩니다

 

for (i in 0 until n) {
        readLine()!!.split(' ').map(String::toInt).forEachIndexed { j, value ->
            if (value == CHICKEN) {
                chicken.add(Pair(i, j))
            } else if (value == HOME) home.add(Pair(i, j))
        }
    }

요런식으로 치킨집과 집 저장 배열에 쑥쑥 넣어줍니다

 

 

( t == m => true입니다. m개의 치킨집을 뽑을 때 그 m이에요 ㅎ)

fun backtracking(count: Int, start: Int,t:Int) {
    if (count == t) {
        tmpAnswer = 0
        home.forEach { h ->
            var tmp = Int.MAX_VALUE
            comPareAnswer.forEach { c ->
                tmp = min(tmp, (abs(h.first - c.first) + abs(h.second - c.second)))
            }
            tmpAnswer += tmp
        }
        answer = min(tmpAnswer, answer)
        return
    }

    for (i in start until chicken.size) {
        if (!visit[i]) {
            visit[i] = true
            comPareAnswer[count] = chicken[i]
            backtracking(count + 1, i, t)
            visit[i] = false
        }
    }


}

이렇게 백트래킹을 돌리며 각 집들과 뽑힌 치킨집과의 '치킨 거리'를 구하며 최솟값을 저장해주면 끝나는 것입니다!~!~!

 

백트래킹 함수가 이해가 잘 안 가신다면 n과m 시리즈를 풀어보시면 이해가 가실꺼에요

( 백준 홈페이지에서 n과m 검색하시면 쭈루룩 나옵니다 아마 11?12?단계까지 있는거로 기억하는데 ㅎ 암튼!! 풀어보세요)

 

전체 코드는 깃허브에 올려놨습니다.

 

봐주셔서 감사합니다!
질문이나 수정되어야 할 부분이 있다면 댓글로 남겨주세요!