코틀린 코딩테스트 강좌, 타임머신으로 빨리 가기

문제 설명

상상해보세요! 미래에서 온 당신은 타임머신을 이용해 특정 시간으로 여행을 하기로 결심합니다. 그러나 이 타임머신은 복잡한 알고리즘을 통해서만 작동할 수 있습니다. 문제는 주어진 시간에 도달하기 위해 최소 몇 번의 점프가 필요한지를 계산하는 것입니다.

문제 정의

정수 S와 E가 주어집니다. S는 시작 시간, E는 도착 시간입니다. 타임머신은 다음과 같은 규칙으로 작동합니다:

현재 시간에서 +1, +2 또는 *2의 연산을 통해 다음 시간으로 점프할 수 있습니다.
타임머신이 작동하는 최소 점프 횟수를 계산하여 출력하는 프로그램을 작성하세요.

입력

첫 번째 줄에 두 정수 S (1 ≤ S ≤ 10⁵)와 E (1 ≤ E ≤ 10⁵)가 주어집니다.

출력

타임머신이 E에 도달하기 위해 필요한 최소 점프 횟수를 출력합니다.

예제

문제 풀이 과정

이 문제는 BFS(Breadth-First Search, 너비 우선 탐색) 알고리즘을 이용해 해결할 수 있습니다. BFS는 특정 노드를 시작으로 해서, 그 노드와 연결된 모든 노드를 탐색한 후, 다음 층의 노드를 탐색하는 방식입니다. 이 문제에서 각 시간대는 그래프의 노드로, 각 점프는 간선으로 표현할 수 있습니다.

단계별 풀이

큐 초기화: BFS를 수행하기 위해 먼저 큐를 초기화합니다. 시작 시간 S와 현재 점프 횟수를 함께 큐에 추가합니다.
방문 배열: 이미 방문한 시간을 기록하기 위해 방문 배열을 생성합니다. 이를 통해 동일한 시간을 중복 방문하는 것을 방지할 수 있습니다.
BFS 수행: 큐에서 노드를 꺼내고, 가능한 모든 점프를 수행하여 다음 시간으로 탐색합니다. 만약 다음 점프가 도착 시간 E에 도달하면, 현재 점프 횟수를 반환합니다.
종료 조건: 도착 시간에 도달하지 못하고 큐가 비게 될 경우, 점프 과정을 중단합니다.

코드 구현


fun minJumps(S: Int, E: Int): Int {
    val queue: Queue> = LinkedList()
    val visited = BooleanArray(100001) // 시간 범위 최대 100000
    queue.add(Pair(S, 0))
    visited[S] = true

    while (queue.isNotEmpty()) {
        val (currentTime, jumps) = queue.poll()

        // 목적지에 도달했을 경우
        if (currentTime == E) {
            return jumps
        }

        // 다음 가능한 시간
        val nextTimes = listOf(currentTime + 1, currentTime + 2, currentTime * 2)

        for (nextTime in nextTimes) {
            if (nextTime in 1..100000 && !visited[nextTime]) {
                visited[nextTime] = true
                queue.add(Pair(nextTime, jumps + 1))
            }
        }
    }
    return -1 // 도달할 수 없는 경우
}

fun main() {
    val input = readLine()!!.split(" ")
    val S = input[0].toInt()
    val E = input[1].toInt()
    println(minJumps(S, E))
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 모든 시간대를 한 번씩 방문하게 되며, 최대 100,000개의 노드에 대해 BFS를 수행하므로 효율적입니다.

결론

이번 강좌에서는 타임머신 문제를 해결하기 위한 BFS 알고리즘을 적용하여 최단 거리를 계산하는 방법을 살펴보았습니다. 코틀린으로 구현하는 과정에서의 장점과 BFS의 기본 원칙을 잘 이해하고 적용하여 코딩 테스트에 활용하시길 바랍니다. 다음 시간에는 다른 문제와 더 다양한 알고리즘을 탐구하는 강좌를 준비하겠습니다!