[백준(BOJ)] 16953 A -> B - 스위프트(Swift)

[Silver II] A → B - 16953

문제 링크

성능 요약

메모리: 81480 KB, 시간: 304 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 그리디 알고리즘

문제 설명

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10⁹)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

풀이

i)

해당 문제는 BFS를 통해 해결하고자 하였습니다. 

첫 번째 값에서 나타날 수 있는 값들을 추가하고,
방문 여부를 체크하면서 만약 구하고자 하는 값이 나타나면 해당 값의 depth를 출력하고자 하였습니다.

 

그림으로 보면 다음과 같습니다.

BFS를 이용한 문제 해결

 

따라서 다음과 같이 코드를 작성하였습니다.

struct Queue {  // 큐 생성
    var que: [Int] = []
    mutating func push(_ x: Int) {
        que.append(x)
    }
    mutating func pop() -> Int {
        que.reverse()
        if let a = que.popLast() {
            que.reverse()
            return a
        }
        return 0
    }
    func empty() -> Bool {
        return que.isEmpty
    }
    func size() -> Int {
        return que.count
    }
}

func bfs(_ a: Int, _ b: Int) -> Int {
    
    var queue = Queue()    
    var visited: [Bool] = Array(repeating: false, count: 100000001)
    var depth: [Int] = Array(repeating: 0, count: 100000001)
    
    queue.push(a)   // 첫 값 넣기
    visited[a] = true
    
    while !queue.empty() {
        let data = queue.pop()
        if data == b {
            break
        }
        
        if data * 2 < 100000001 && !visited[data * 2] { // 2의 배수 넣기
            queue.push(data * 2)
            visited[data * 2] = true
            depth[data * 2] = depth[data] + 1
        }
        
        if data * 10 + 1 < 100000001 && !visited[data * 10 + 1] {   // 마지막 자리에 +1 추가하기
            queue.push(data * 10 + 1)
            visited[data * 10 + 1] = true
            depth[data * 10 + 1] = depth[data] + 1
        }
        
    }
    
    
    return depth[b] == 0 ? -1 : depth[b] + 1
    
}



let ab = readLine()!.split(separator: " ").map { Int($0)! }
let (a, b) = (ab[0], ab[1])
print(bfs(a, b))

→ 런타임 에러

visited 배열과 depth 배열의 크기가 매우 커서 나타난 에러라고 생각하였습니다.

 

ii)

데이터 값과 깊이를 함께 저장하고, 방문 여부를 set을 통해 해결하였습니다.

 

다음과 같이 변경하였습니다.

import Foundation

// Queue를 위한 구조체 정의
struct Queue<T> {
    private var elements: [T] = []
    
    mutating func enqueue(_ element: T) {
        elements.append(element)
    }
    
    mutating func dequeue() -> T? {
        return elements.isEmpty ? nil : elements.removeFirst()
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
}

func findMinOperations(_ a: Int, _ b: Int) -> Int {
    var queue = Queue<(Int, Int)>()
    var visited = Set<Int>()
    
    queue.enqueue((a, 0))
    visited.insert(a)
    
    while !queue.isEmpty {
        let (current, operations) = queue.dequeue()!
        
        if current == b {
            return operations + 1
        }
        
        let double = current * 2
        let appendOne = current * 10 + 1
        
        if double <= b && !visited.contains(double) {
            queue.enqueue((double, operations + 1))
            visited.insert(double)
        }
        
        if appendOne <= b && !visited.contains(appendOne) {
            queue.enqueue((appendOne, operations + 1))
            visited.insert(appendOne)
        }
    }
    
    return -1  // B를 만들 수 없는 경우
}

// 입력 받기
let input = readLine()!.split(separator: " ").map{ Int($0)! }
let a = input[0]
let b = input[1]

let result = findMinOperations(a, b)
print(result)

 

만약 메모리가 초과된다면 Set 등을 사용하여 메모리를 초과하지 않도록 해야함을 배웠습니다.