[백준] 9205번: 맥주 마시면서 걸어가기 - Kotlin[코틀린]

문제

 

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

 

---

풀이

 

 문제에서 주어진 집, 편의점, 페스티벌의 좌표를 그래프의 형태로 가공하여 BFS를 활용해 문제를 해결할 수 있다.

 

 상근이는 매 50미터마다 맥주 한 병을 마셔야 하며, 최대 20병의 맥주를 들고 다닐 수 있다. 따라서 시작 위치에서 20 X 50 = 1000미터 이내라면 이동할 수 있는 지점이다. 이를 고려하여 집, 편의점, 페스티벌 장소를 각각의 정점으로 하고 정점 간의 거리가 1000미터 이내에 있으면 도착 가능한 거리라고 간주하여 그래프로 연결할 수 있다.

 

이후에는 BFS를 이용하여 도착 가능 여부를 확인하면 된다.

 

---

코드

 

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

data class Point(val x: Int, val y: Int)

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val sb = StringBuilder()
    repeat(br.readLine().toInt()) {
        val num = br.readLine().toInt()
        val list = mutableListOf<Point>()
        repeat(num + 2) {
            val (x, y) = br.readLine().split(' ').map { it.toInt() }
            list.add(Point(x, y))
        }
        val graph = List(num + 2) { mutableListOf<Int>() }
        
        for(i in 0 until list.size) { // 정점끼리 거리 비교
            for(j in i + 1 until list.size) {
                val a = list[i]
                val b = list[j]
                if(abs(a.x-b.x) + abs(a.y-b.y) > 1000) continue // 1000미터 이상이면 연결 불가능
                graph[i].add(j)
                graph[j].add(i)
            }
        }

        fun bfs(): Boolean {
            val queue: Queue<Int> = LinkedList()
            val visited = BooleanArray(num+2)
            queue.add(0)
            visited[0] = true

            while (queue.isNotEmpty()) {
                val cur = queue.poll()
                if(cur == num + 1) return true // 도착
                for(next in graph[cur]) {
                    if(visited[next]) continue
                    visited[next] = true
                    queue.add(next)
                }
            }
            return false
        }

        sb.append(if(bfs()) "happy\n" else "sad\n")
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}