[알고리즘/Swift] 16953 A -> B

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 16953 A -> B
• 제출 언어: Swift
• 알고리즘 분류:
  • 그래프 이론
  • 그리디 알고리즘
  • 그래프 탐색
  • 너비 우선 탐색

---

풀이

숫자 A에서 B로 만드려면 2를 곱하기와 맨 뒷 자리에 1 붙이기를 반복해야 한다. 만약 예를 들어 2부터 시작한다면, 4와 21로 만들 수 있고, 또 4로는 8과 41, 21로는 42와 211을 만들 수 있다. 하나의 숫자로 두 개의 수를 만들 수 있으므로 다음과 같은 피라미드 형태의 수열이 생긴다.

우리가 구하려는 것은 필요한 연산의 최솟값이므로 BFS로 Depth별로 탐색하여, B의 숫자에 도달하면 해당 Depth를 반환하고, 도달하지 못하는 경우 -1을 반환하는 알고리즘을 작성하였다

BFS 적용

• 먼저 처음 숫자인 A를 queue에 넣은 다음 queue에 원소가 없어질 때까지 queue의 가장 앞 부분을 target으로 꺼내서 2를 곱한 값과, 1을 뒤에 붙인 값을 queue에 넣어준다
• 만약 target값이 B가 되었다면 해당 Depth를 반환한다
• 만약 target값이 B를 넘겼다면 더 이상 연산해줄 필요가 없어지므로 continue한다
• B에 도달했을 때의 최종 Depth를 구하기 위해서 queue에 연산한 값과 함께 depth + 1값을 계속 넣어준다

전체 코드

import Foundation

let n = readLine()!.split(separator: " ").map{Int(String($0))!}
let (A,B) = (n[0], n[1])
func makeNum(_ A: Int, _ B: Int) -> Int {
    var queue: [(num: Int,count: Int)] = [(A, 1)]
    while !queue.isEmpty {
        let target = queue.removeLast()
        if target.num == B {
            return target.count
        }
        if target.num > B {
            continue
        }
        queue.append(((target.num * 10 + 1), target.count + 1))
        queue.append((target.num*2, target.count + 1))
    }
    return -1
}
print(makeNum(A, B))