[백준/코틀린] 16953번: A → B

링크

16953번: A → B

개요

A를 B로 바꾸는 데 필요한 최소 연산 횟수를 두 가지 방식으로 구현합니다.

• 풀이 1: BFS
• 풀이 2: Greedy Algorithm

풀이 1: BFS

A와 B 사이의 모든 숫자를 그래프의 정점으로 보고,
각 숫자에서 주어진 연산을 통해 이동할 수 있는 상태를 그래프의 간선으로 본다면,
시작 숫자에서 목표 숫자로 가는 최단 거리를 구하는 BFS 문제로 볼 수 있습니다.

BFS를 통해 A에서 B까지의 최단거리를 구합니다.

두 연산의 결과는 항상 다른 값을 만들기 때문에,
정점을 이미 방문했는지 체크할 필요가 없습니다.

코드

val mul = listOf(2, 10)
val add = listOf(0, 1)

fun bfs(start: Long, target: Long) {
    val queue = ArrayDeque<Pair<Long, Int>>()

    queue.addLast(start to 0)
    while (queue.isNotEmpty()) {
        val (current, depth) = queue.removeFirst()

        if (current == target) return println(depth + 1)
        repeat(2) {
            val next = mul[it] * current + add[it]

            if (next <= target) {
                queue.addLast(next to depth + 1)
            }
        }
    }

    println(-1)
}

fun main() {
    val (a, b) = readln().split(" ").map { it.toLong() }

    bfs(a, b)
}

풀이 2: Greedy Algorithm

어떤 숫자 B가 주어졌을 때, 그것을 만들 수 있는 이전 숫자가 유일하게 결정되기 때문에,
정방향(A → B)에서는 분기가 생기지만 역방향(B → A)에서는 분기가 존재하지 않습니다.
즉, 어떤 숫자 B에 적용할 수 있는 역연산은 최대 하나뿐입니다.

B의 마지막 자리가 1이라면 뒤의 1을 제거하고,
그렇지 않고 B가 짝수라면 2로 나눕니다.

그리디한 방식으로 B를 A로 바꾸는 데 필요한 연산의 최솟값을 구합니다.

코드

fun main() {
    var (a, b) = readln().split(" ").map { it.toLong() }
    var ans = 0

    while (true) {
        when {
            a == b -> return println(ans + 1)
            a > b -> return println(-1)
            b % 10 == 1L -> b /= 10
            b % 2 == 0L -> b /= 2
            else -> return println(-1)
        }
        ans++
    }
}