[백준 16953] A -> B (Swift)

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

 

BFS

정수 A, B (예, 2, 162) 가 주어지면, A에서 B가 되기까지 두가지 연산을 수행할 수 있다고 할 때, 최소 몇번 수행해야 되는지 출력하는 문제, 불가능하면 -1 출력

 

접근방법

BFS나 DFS 완전탐색 문제 풀이할 때는 늘 갈 수 있는 경로 를 생각하면서 푸는데, 이게 문제가 격자판에서 어쩌구 할 경우에는 갈 수 있는 칸이 되고, 지금 문제같은 경우는 가능한 연산 두가지가 된다. 현재 갖고 있는 수에서 2를 곱하는 길 or 1을 가장 오른쪽에 붙이는 길

 

B까지 도달하는 최단 거리를 구하는 거니까 BFS가 더 효율적인 것 같아서 큐를 사용해서 풀었다.

큐의 원소는 두개의 Int를 갖는 튜플로, 첫번째 수는 현재 수, 두번째 수는 현재 수까지 도달하는데 수행한 연산의 수 이다.

따라서 현재 수가 B가 될 때 두번째 수가 답이 된다.

 

현재 수가 B보다 작기만 하면 두가지 연산을 모두 수행한 값을 큐에 삽입했다.

 

소스코드

import Foundation

func solution() -> Int {
    
    let ab: [Int] = (readLine()?.split(separator:" ").map { Int($0)! })!
    let a:Int = ab[0]
    let b:Int = ab[1]
    
    var q:[(Int,Int)] = [(a,1)]
    
    while !q.isEmpty {
        let now = q.removeFirst()
        if now.0 == b {
            return now.1
        }
        else if now.0 < b {
            q.append((now.0*2, now.1+1))
            q.append((now.0*10+1, now.1+1))
        }
    }
    
    return -1
    
}

print(solution())