[백준 1697][Kotlin] 숨바꼭질

문제 링크

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

코드

import java.util.ArrayDeque

fun main() {
    val (start, end) = readln().split(' ').map { it.toInt() }
    if (start == end) {
        print(0)
        return
    }
    val deque = ArrayDeque<Array<Int>>()
    val dx = listOf(1, -1, 2) // +, +, *
    val visitsSize = if (start > end) start*2 else end*2 // 수빈이가 항상 동생보다 뒤에 있는 것은 아니기 때문에 방문 배열 크기는 더 큰 수를 기준으로 정함
    val visits = Array(visitsSize+1) {false} // 방문을 기록해야 메모리/시간초과 발생하지 않음
    deque.offerLast(arrayOf(start, 0))

    while (deque.size > 0) { // Queue로 bfs 구현
        val node = deque.pollFirst()
        for (i in 0 until 3) {
            var tempValue = node[0]
            if (i == 2)
                tempValue *= dx[i]
            else
                tempValue += dx[i]

            if (!(tempValue in 0 .. visitsSize) || visits[tempValue])
                continue
            if (tempValue == end) {
                print(node[1]+1)
                return
            }
            deque.offerLast(arrayOf(tempValue, node[1]+1))
            visits[tempValue] = true
        }
    }
}

설명

그래프의 깊이가 곧 동생을 찾을 수 있는 가장 빠른 시간(초)이다. 한 시점에서 3가지의 경우가 발생하기 때문에 이를 전부 탐색하여 맞는 값을 찾으려면 bfs 기법을 이용해야한다.

후기

값을 더하고 빼고 곱하다보면 이전 값과 같아질 수 있다. 따라서 메모리 초과가 나지 않으려면 방문을 기록하여 중복 방문을 방지해야한다.
예제에는 수빈이가 동생보다 뒤에 있는 케이스 밖에 없지만 문제에서 경우를 제한하지 않았다면 수빈이가 동생보다 앞에 있는 케이스까지 고려하자.