[백준]1697번: - kotlin

8843 단어 BFSBFS

문제

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

풀이

  • 현재 위치를 x 라고 하면 x 는 항상 3개의 자식을 갖는다. (범위 내에 있다면)
  • 자식의 범위를 확인하고, 방문하지 않은 곳이라면 방문한다.
  • n 이 60000 이고, k 가 100000 일때 n2 한 값에서 점차 내려오는 과정이 더 빠를거라고 생각했지만, 60000 만에서 50000을 만들고 100000 으로 가는게 훨씬 효율적이다!! 그렇기 때문에 n2 를 할 때 범위는 100000 이하일 때에만 하는 것이 좋다!
import java.util.*

fun traverse(queue: Queue<Pair<Int, Int>>, visited: Array<Boolean>, nDest: Int, count: Int) {
    if (nDest in 0 until 100001 && !visited[nDest]) {
        queue.add(Pair(nDest, count + 1))
        visited[nDest] = true
    }
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, k) = br.readLine().split(" ").map { it.toInt() }
    val queue: Queue<Pair<Int, Int>> = LinkedList()
    val visited = Array(100001) { false }
    queue.add(Pair(n, 0))
    visited[n] = false
    var result = 0
    while (queue.isNotEmpty()) {
        val (dest, count) = queue.poll()
        if (dest == k) {
            result = count
            break
        }
        traverse(queue, visited, dest + 1, count)
        traverse(queue, visited, dest - 1, count)
        traverse(queue, visited, dest * 2, count)
    }
    bw.write("$result")
    br.close()
    bw.close()
}

더 좋은 방법 있으면 댓글 달아주세요!!!

좋은 웹페이지 즐겨찾기