[백준][코틀린][13913] 숨바꼭질4

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

13913번: 숨바꼭질 4

문제 풀이

1. https://www.acmicpc.net/problem/1697 와 동일하게 BFS 를 이용하여 푼다.

2. 출력에서 최단 시간의 지난 경로를 출력해야 한다.

3. 경로를 출력하기 위해서 방문 배열(visit) 를 이용한다.

4. 이때 방문 배열을 기존과 같은 BooleanArray 가 아닌 IntArray 로 선언한다.

5. visit 배열에 visit[next] = currentPosition 으로 저장을 한다.

6. 최단 시간이 되었을 때 visiti 배열을 K -> N 으로 역으로 탐색하여 결과를 출력한다.

7. 마지막으로 방문배열은 -1 로 초기화 하여 선언한다. N, K 가 0도 될 수 있기 때문에 0 으로 초기화하게 되면 메모리 초과 에러가 발생한다.

코드

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() }

    bfs(N, K)
}

private fun bfs(N: Int, K: Int) {
    val queue = LinkedList<Pair<Int, Int>>()
    val visit = IntArray(100001) { -1 }
    queue.add(Pair(N, 0))

    while (queue.isNotEmpty()) {
        val (curPosition, curTime) = queue.pop()

        if (curPosition == K) {
            println(curTime)

            val result = mutableListOf<Int>()
            var nextK = K
            result.add(nextK)

            if (nextK != N) {
                while (true) {
                    //println("$nextK, ${visit[nextK]}")
                    result.add(visit[nextK])
                    nextK = visit[nextK]

                    if (nextK == N) break
                }
            }

            val sb = StringBuilder()

            for (i in result.size - 1 downTo 0 step 1) {
                sb.append("${result[i]} ")
            }
            println(sb.toString())

            return
        }

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

            if (nextPosition < 0 || nextPosition > 100000) continue
            if (visit[nextPosition] != -1) continue

            //println("curPosition : $curPosition, nextPosition : $nextPosition")
            visit[nextPosition] = curPosition
            queue.add(Pair(nextPosition, curTime + 1))
        }
    }
}