[백준] 9205번 맥주마시면서 걸어가기

9205번 맥주마시면서 걸어가기

접근 방법

맥주는 편의점에 가면 무조건 20병이 채워지므로 점과 점사이의 거리가 1000m이하면 어디든 갈 수 있고 다시 20병으로 채워지므로 1000m를 기준으로 갈 수 있는 곳이 있는지 없는지 구분하였다

한 점을 기준으로 갈 수 있는 모든 편의점을 queue에 넣는다.
위와 같은 방식으로 queue에서 빼고 넣고를 반복하여 bfs를 이용하여 문제를 풀었다.
그리고 각 점마다 festival 위치와 1000m 이하 차이가나면 갈 수 있으므로 뒤에를 더 보지 않고 break를 걸어 나왔다.

만약 while문이 다 돌면 갈 수 있는 방법이 없으므로 sad를 정답에 포함시킨다.

시간복잡도

testCount cvsNum cvsNum
bigO(50100100)

code

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.abs

fun main() {
    val io = StandardIO()
    val testNum = io.getIntFromBr()
    val ansList = mutableListOf<String>()
    repeat(testNum) {
        val cvsNum = io.getIntFromBr()
        val house = io.getPosFromBr()
        val cvsList = mutableListOf<Pos>().apply {
            repeat(cvsNum) { add(io.getPosFromBr()) }
        }
        val festival = io.getPosFromBr()
        var beer = 20
        var success = false
        val visited: Array<Boolean> = Array(cvsNum) { false }
        val queue = mutableListOf(house)
        while (queue.isNotEmpty()) {
            val now = queue.removeFirst()
            if (getDistance(now, festival) <= beer * 50)  {
                success = true
                break
            }
            for (i in cvsList.indices) {
                if (!visited[i] && getDistance(now, cvsList[i]) <= beer * 50) {
                    queue.add(cvsList[i])
                    visited[i] = true
                }
            }
        }
        ansList.add(if (success) "happy" else "sad")
    }
    ansList.forEach { println(it) }
}

fun getDistance(pos1: Pos, pos2: Pos): Int {
    return abs(pos2.x - pos1.x) + abs(pos2.y - pos1.y)
}

class StandardIO {
    private val br = BufferedReader(InputStreamReader(System.`in`))

    fun getIntFromBr(): Int = br.readLine().toInt()

    fun getPosFromBr(): Pos {
        val (x,y) = br.readLine().split(" ").map{ it.toInt() }
        return Pos(x, y)
    }
}