[BOJ/백준][Silver1] 16953 : A → B (Kotlin)

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

16953번: A → B

 

 

[난이도] Silver1
[유형] BFS

[풀이]
BFS로 해결해야 하는 문제인데 숫자의 범위가 커서 배열이 아닌 set으로 메모제이션을 해야합니다.
범위는 크지만 2배 혹은 자릿수를 늘리는(10배뒤 1을 더하는) 연산밖에 없기 때문에 나올 수 있는 수가
별로 없어서 메모리가 초과가 발생하지 않습니다.
풀고나서 생각해보니 어떤 수든 한번밖에 나올 수밖에 없어서 메모제이션도 해줄 필요가 없었습니다.
x2 연산으로 나오는 수와 1을 붙히는 연산과 겹치는 수가 나올 수 없기 때문입니다.

 

import java.util.*
import kotlin.collections.HashSet
val bw = System.`out`.bufferedWriter()
fun main() = with(System.`in`.bufferedReader()){
    var (A,B) = readLine().split(' ').map{it.toLong()}
    var st = HashSet<Long>()
    var q:Queue<Long> = LinkedList<Long>()
    q.add(A)
    st.add(A)
    var ans=0
    while(!q.isEmpty()){
        var sz = q.size
        ans++
        while(sz-->0) {
            var cur = q.poll()
            if(cur==B){
                bw.write("$ans")
                bw.flush()
                return
            }
            if (cur * 2 <= B && !st.contains(cur * 2)) {
                st.add(cur * 2)
                q.add(cur * 2)
            }
            if (cur * 10 + 1 <= B && !st.contains(cur * 10 + 1)) {
                st.add(cur * 10 + 1)
                q.add(cur * 10 + 1)
            }
        }
    }
    bw.write("-1")
    bw.flush()
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/16953.kt