백준 1686번 복날 Kotlin

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

문제

---

생각하기

---

• BFS 문제이다.

동작

유클리드 거리 법을 활용해 거리를 구하고 최대 시간 안에 목표지점까지 도달하는지 파악하면 된다.

결과

코드

---

import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var V = 0
private var M = 0
private var max: Double = 0.0
private lateinit var start: Node
private lateinit var dest: Node
private var count = 0
private lateinit var bunkers: MutableList<Node>

private data class Node(val x: Double, val y: Double, val count: Int) {
    constructor(x: Double, y: Double) : this(x, y, 0) {

    }
}

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    if (BFS()) {
        sb.append("No.")
    } else {
        sb.append("Yes, visiting $count other holes.")
    }

    return sb.toString()
} // End of solve()

private fun BFS(): Boolean {
    val N = bunkers.size
    val isVisited = BooleanArray(N)
    val que = ArrayDeque<Node>()
    que.addLast(Node(start.x, start.y, 0))

    while (que.isNotEmpty()) {
        val cur = que.removeFirst()

        if (dist(cur.x, cur.y, dest.x, dest.y) < max) {
            count = cur.count
            return false
        }

        for (i in 0 until N) {
            if (isVisited[i]) continue
            val node = bunkers[i]

            if (dist(cur.x, cur.y, node.x, node.y) < max) {
                isVisited[i] = true
                que.addLast(Node(node.x, node.y, cur.count + 1))
            }
        }
    }

    return true
} // End of BFS()

private fun dist(x1: Double, y1: Double, x2: Double, y2: Double): Double {
    return Math.hypot(x1 - x2, y1 - y2)
} // End of dist()

private fun input() {
    var st = StringTokenizer(br.readLine())
    V = st.nextToken().toInt()
    M = st.nextToken().toInt()
    max = V * M * 60.0

    bunkers = mutableListOf()
    st = StringTokenizer(br.readLine())
    start = Node(st.nextToken().toDouble(), st.nextToken().toDouble(), 0)

    st = StringTokenizer(br.readLine())
    dest = Node(st.nextToken().toDouble(), st.nextToken().toDouble(), 0)


    while (true) {
        val line: String? = br.readLine()
        if (line.isNullOrEmpty()) break

        st = StringTokenizer(line)
        val x = st.nextToken().toDouble()
        val y = st.nextToken().toDouble()
        bunkers.add(Node(x, y))
    }

} // End of input()