[백준] 1697 - 숨바꼭질

BFS를 활용하는 그래프 문제.
그래프인 이유는 X - 1, X + 1 와 같은 역연산이 서로 존재하기 때문에 노드가 순환할 수 있기 때문이다.

정점1 - X + 1, 정점2 - X - 1, 정점3 - 2 * x 을 ArrayDeque 에 추가하고 출력값이 K 와 같아졌을때 time 을 출력하자.

풀이

/*
* 사이클이 존재하므로 그래프. 가장 빠른 시간 출력이므로 BFS.
* 루트 - N
* 노드1 - X-1
* 노드2 - X+1
* 노드3 - 2*X
* */
fun `1697-숨바꼭질`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, k) = br.readLine().split(" ").map { it.toInt() }
    // first = 점, second = 시간
    val arrayDeque = ArrayDeque<Pair<Int, Int>>()
    var result = 0
    val visitedArr = BooleanArray(100_001)

    arrayDeque.add(n to result)
    visitedArr[n] = true

    while(arrayDeque.isNotEmpty()){
        val from = arrayDeque.removeFirst()
        val x = from.first
        val time = from.second

        if(x == k){
            result = time
            break
        }

        val node1 = x - 1
        val node2 = x + 1
        val node3 = 2 * x

        arrayDeque.addNode(node1, time, visitedArr)
        arrayDeque.addNode(node2, time, visitedArr)
        arrayDeque.addNode(node3, time, visitedArr)
    }

    bw.write(result.toString())
    bw.flush()
    bw.close()
    br.close()
}

/*
* k 는 0 ~ 10만이므로 제한을 준다.
* x - 1, x + 1 등에서 재방문 할 수 있기 때문에 visited 설정
* */
private fun ArrayDeque<Pair<Int, Int>>.addNode(node: Int, time: Int, visitedArr: BooleanArray){
    if(node in 0 .. 100_000 && !visitedArr[node]){
        visitedArr[node] = true
        this.addLast(node to time + 1)
    }
}