[백준][코틀린][1697] 숨바꼭질

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

1697번: 숨바꼭질

문제 풀이

1. N 을 시작 지점, K 를 목표 지점으로 하여 BFS 를 수행한다.

2. 이때 시작 시점과 목표 지점이 같으면 탐색을 종료 한다.

3. 큐에는 (시작 지점, 현재까지의 걸린 시간) 을 저장한다.

4. BFS 에서 (앞으로 걷는 경우, 뒤로 걷는 경우, 순간 이동 하는 경우) 에 대해서 탐색한다.

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, K) = br.readLine().split(" ").map { it.toInt() }
    println("${bfs(N, K)}")
}

private fun bfs(start: Int, K: Int): Int {
    val queue = LinkedList<Pair<Int, Int>>()
    queue.add(Pair(start, 0))
    val visit = BooleanArray(100001) { false }
    visit[start] = true
    var result = 0

    while (queue.isNotEmpty()) {
        val (curPosition, curTime) = queue.pop()
        //println("curPosition : $curPosition, curTime : $curTime")

        if (curPosition == K) {
            result = curTime
            break
        }

        for (i in 0..2) {
            val next = when (i) {
                0 -> curPosition - 1
                1 -> curPosition + 1
                else -> curPosition * 2
            }

            if (next < 0 || next > 100000) continue
            if (visit[next]) continue

            visit[next] = true
            queue.add(Pair(next, curTime + 1))
        }

    }

    return result
}