[알고리즘/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))