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

문제

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

해설

문제에서 상근이는 집에서 맥주 한 박스를 들고 출반한다. 이때 한 박스에는 20개의 맥주가 들어있다.

50미터 당 맥주 한 병을 마시므로 최대 1000미터까지 움직일 수 있고, 이후에는 맥주를 새로 사거나 이미 페스티벌에 도착했어야 한다.

 

이 문제를 해결하기 위해서는 매허튼 거리를 계속해서 계산해주어야 한다.

맨허튼 거리란 두 좌표 사이의 x 좌표의 차이 + y 좌표의 차이를 뜻한다.

만약 집 위치와 락 페스티벌의 멘허튼 거리가 1000이 안된다면, 맥주 한박스로 페스티벌에 도착할 수 있게 되는 것이다.

하지만 1000이 넘는다면, 중간에 편의점을 들려 맥주를 사야한다.

따라서 집과 편의점의 맨허튼 거리를 구하여 1000이 안된다면, 이 편의점의 위치를 큐에 넣어 위치를 갱신해주며 bfs를 수행해 나가면 된다.

코드

import java.util.*
import kotlin.math.abs

private var homePos = Pair(0, 0)
private lateinit var storePos: Array<Pair<Int, Int>>
private var festivalPos = Pair(0, 0)
private lateinit var visited: BooleanArray

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()

    repeat(testCase) {
        val storeCnt = readLine().toInt()
        visited = BooleanArray(storeCnt)

        val home = readLine().split(" ").map { it.toInt() }
        homePos = Pair(home[0], home[1])

        storePos = Array(storeCnt) { Pair(0, 0) }
        repeat(storeCnt) { i ->
            val store = readLine().split(" ").map { it.toInt() }
            storePos[i] = Pair(store[0], store[1])
        }

        val festival = readLine().split(" ").map { it.toInt() }
        festivalPos = Pair(festival[0], festival[1])

        val possible = move()

        if(possible) println("happy")
        else println("sad")
    }
}

private fun move(): Boolean {
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(homePos)

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curX = cur.first
        val curY = cur.second

        if(manhattan(curX, curY, festivalPos.first, festivalPos.second) <= 1000) return true
        else {
            for(i in storePos.indices) {
                if(manhattan(curX, curY, storePos[i].first, storePos[i].second) <= 1000 && !visited[i]) {
                    visited[i] = true
                    que.add(Pair(storePos[i].first, storePos[i].second))
                }
            }
        }
    }

    return false
}

private fun manhattan(startX: Int, startY: Int, endX: Int, endY: Int): Int
= abs(startX - endX) + abs(startY - endY)