[백준/BOJ] 2247번: 숨바꼭질 4

문제

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

13913번: 숨바꼭질 4

해설

https://jjunsu.tistory.com/197

[백준/BOJ] 1697번: 숨바꼭질

저번에 풀었던 숨바꼭질 문제에서 업그레이드 된 문제이다.

위 문제와의 차이점은 이동한 경로도 출력해야 한다는 것이다.

 

해당 지점에 방문하기 전 지점을 route 배열에 기록을 해주었다.

동생을 찾았다면 저장해놓은 배열을 역순으로 출력시키면 된다.

소스 코드

import java.util.*

private var n = 0
private var m = 0
private var totalCnt = 0
private val path: Deque<Int> = LinkedList()
private val route = IntArray(100001)
private val visited = BooleanArray(100001)

fun main() {
    input()
    find()
    println(totalCnt)
    while(path.isNotEmpty()) print("${path.pollLast()} ")
}

private fun input() = with(System.`in`.bufferedReader()) {
    val st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
}

private fun find() {
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(n, 0))
    visited[n] = true

    while(que.isNotEmpty()) {
        val idx = que.peek().first
        val cnt = que.peek().second
        que.poll()

        if(idx == m) {
            var temp = idx

            while(temp != n) {
                path.add(temp)
                temp = route[temp]
            }
            path.add(n)
            totalCnt = cnt

            return
        }

        if(idx + 1 in 0 until 100001 && !visited[idx + 1]) {
            que.add(Pair(idx + 1, cnt + 1))
            visited[idx + 1] = true
            route[idx + 1] = idx
        }
        if(idx - 1 in 0 until 100001 && !visited[idx - 1]) {
            que.add(Pair(idx - 1, cnt + 1))
            visited[idx - 1] = true
            route[idx - 1] = idx
        }
        if(idx * 2 in 0 until 100001 && !visited[idx * 2]) {
            que.add(Pair(idx * 2, cnt + 1))
            visited[idx * 2] = true
            route[idx * 2] = idx
        }
    }
}