백준 1697번: 숨바꼭질 (Kotlin)

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

1697번: 숨바꼭질

 

풀이

DP로 풀 수 있을 것 같았는데 방법이 떠오르지 않아서 우선 BFS를 사용했다. 매초마다 이전 위치들에서 도착할 수 있는 모든 위치로 움직이기 때문에 가장 처음 목표지점에 도착했을 때가 최단 시간이 된다.

또한, 곱하기2로 범위를 절반씩 줄일 수 있으므로 O(log^N) 시간으로 문제를 해결할 수 있다

 

BFS 과정에서 당연하지만 이전에 방문했던 점은 다시 방문하지 않아야 하는데, 이전보다 시간이 더 흐른 상태에서 같은 연산을 반복하기 때문이다. 따라서 방문표시를 할 배열이 필요한데, 크기를 어느 정도로 잡아야할지 고민이 됐다. 예를 들어 50,001 (x2) -> 100,002 (-1) (-1) -> 100,000 와 같이 최대 범위를 초과했다가 마이너스로 가는 경우도 있을 것 같았기 때문이다. 

 

결과적으로, 50,001 (-1) -> 50,000 (x2) -> 100,000처럼 최대 범위를 넘어서는 경우보단 숫자를 먼저 몇 번 빼고 x2를 하는게 항상 더 빨리 갈 수 있다. 그리고 절반인 50,000을 기준으로 숫자가 커질수록 그 차이는 훨씬 커진다.

ex)

1. 50,004 (x2) -> 100,008 (-8) -> 100,000 ==> 9번

2. 50,004 (-4) ->  50,000 (x2) -> 100,000 ==> 6번

 

따라서, 방문 가능 범위를 0 ~ 100,000으로 제한해도 문제를 해결할 수 있다.

 

 

개인적으로 처음엔 여기까지 생각하지 못해서 안전하게 최대 200,000까지 방문 가능하도록 했는데, 정답을 받을 수 있었다.

 

이후에 궁금해서 찾아봤는데, 최대 범위를 넘어서는 경우가 없는건 k의 최대 값이 짝수이기 때문이었다.

9 -> 15  ==>  9 -> 8 ->16 -> 15 의 케이스처럼, 최대 값이 홀수라면 최대 값을 넘어서고 마이너스로 가는 케이스가 존재할 수 있기 때문이다.

하지만 처음 문제를 풀 땐 생각하기 어려울 수 있기 때문에, 그럴 땐 범위를 충분히 안전하게 설정해서 푸는 게 좋을 것 같다.     

 

코드

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

// 250_000을 이상인 모든 수 n은
// (n * 2) 이후 -1씩 계산해주는 것보다
// -1을 먼저 몇 번 빼고 n * 2를 하는 게 항상 더 빠르다
// ex) 250_001 * 2 = 500_002 -> 500_000 ==> 3번 계산
// ex) 250_001 -> 250_000 -> 500_000 ==> 2번 계산
// 250_001에서 수가 커질 수록 차이는 더 커진다.
const val MAX_POSITION = 100_000

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val myPosition = input[0].toInt()
    val goal = input[1].toInt()

    val visited = BooleanArray(MAX_POSITION + 1)    // 방문 처리 배열
    val queue: Queue<Pair<Int, Int>> = LinkedList() // 위치, 지난 시간
    queue.offer(Pair(myPosition, 0))
    visited[myPosition] = true

    while (queue.isNotEmpty()) {
        val pair = queue.poll()
        val position = pair.first
        val time = pair.second

        if (position == goal) { // 동생을 찾았으면 종료
            print(time)
            return
        }

        // -1을 거쳐가는 최단경로는 존재할 수 없다
        val nextPosition1 = position - 1
        if (nextPosition1 >= 0 && visited[nextPosition1].not()) {
            visited[nextPosition1] = true
            queue.offer(Pair(nextPosition1, time + 1))
        }

        // 현재 위치가 동생의 위치보다 크면 증가 연산을 할 필요가 없다.
        if (position < goal) {
            val nextPosition2 = position + 1
            // 최대 범위를 넘었다가 왼쪽으로 가는 경로보다 더 빠른 경로가 항상 존재한다.
            if (nextPosition2 <= MAX_POSITION && visited[nextPosition2].not()) {
                visited[nextPosition2] = true
                queue.offer(Pair(nextPosition2, time + 1))
            }

            val nextPosition3 = position * 2
            if (nextPosition3 <= MAX_POSITION && visited[nextPosition3].not()) {
                visited[nextPosition3] = true
                queue.offer(Pair(nextPosition3, time + 1))
            }
        }
    }
}