백준 9019번: DSLR

문제 분석

0 이상 10000 미만의 십진수 A와 B가 입력으로 주어졌을 때, A를 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력합니다.

명령어는 다음과 같이 4개입니다.

• D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.

• S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.

• L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.

• R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

접근 방법

명령어가 4개 존재하기 때문에 A에서 특정 수로 변환될 수 있는 경우의 수는 총 4개입니다.

A가 1234라고 가정했을 때, 4개의 명령어에 의해서 각각 2468, 1233, 2341, 4123 으로 변환될 수 있습니다.
또한, 각 수들은 4개의 명령어에 의해서 또 다른 값으로 변환될 수 있습니다.
이러한 형태로 쭉 뻗어 나가다가 B가 나왔을 때, 현재까지 사용한 명령어를 출력하면 됩니다.

이 때, 최소한의 명령어 나열을 구하기 위해서 BFS(너비우선탐색) 알고리즘을 사용하면 될 것입니다.

첫번째 코드 (시간 초과)

struct Queue<T: Comparable> {
    typealias ValueType = (T, String)
    
    private var inbox: [ValueType] = []
    private var outbox: [ValueType] = []
    
    var isEmpty: Bool { return inbox.isEmpty && outbox.isEmpty }
    var size: Int { return inbox.count + outbox.count }
    
    mutating func enqueue(_ value: ValueType) { inbox.append(value) }
    
    @discardableResult
    mutating func dequeue() -> ValueType? {
        if outbox.isEmpty {
            outbox.append(contentsOf: inbox.reversed())
            inbox = []
        }
        
        return outbox.isEmpty ? nil : outbox.removeLast()
    }
}
let T = Int(readLine()!)!
for _ in 0..<T {
    let ab = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (ab[0], ab[1])
    
    var queue = Queue<Int>()
    queue.enqueue((a, ""))
    var visited: Set<Int> = []
    visited.insert(a)
    
    while !queue.isEmpty {
        let v = queue.dequeue()!
        if v.0 == b {
            print(v.1)
            break
        }
        
        for op in OperationCode.allCases {
            let newValue = operate(n: v.0, op: op)
            if !visited.contains(newValue) {
                queue.enqueue((newValue, v.1 + op.rawValue))
                visited.insert(newValue)
            }
        }
    }
}

enum OperationCode: String, CaseIterable {
    case D, S, L, R
}

func operate(n: Int, op: OperationCode) -> Int {
    switch op {
    case .D: // n을 2배
        return n * 2 % 10000
    case .S: // n-1
        return n == 0 ? 9999 : n - 1
    case .L: // n을 왼편으로 회전
        return n % 1000 * 10 + n / 1000
    case .R: // n을 오른편으로 회전
        return n % 10 * 1000 + n / 10
    }
}

처음에는 A에서 B로 변환하는데 필요한 명령어 나열을 큐의 튜플에 문자열 형태로 저장했습니다.
하지만, 시간 초과가 났고 원인을 알아내지 못해 구글링한 결과 Swift에서는 문자열을 더하는 연산은 상수 시간에 가능하지만, 일반적으로 정수 덧셈 연산 보다는 느리기 때문이라고 합니다.

따라서 문자열을 직접 저장하지 않고, 명령어에 따른 정수값을 누적하여 시간 초과 문제를 해결해야합니다.

D = 1, S = 2, L = 3, R = 4 로 가정했습니다.
예를 들어, 누적된 정수값이 1123인 경우 DDSL을 의미합니다.

또한, 방문 노드 체크를 위한 자료구조로 Set을 사용했는데 Set은 insert, remove, contains 연산이 모두 O(1) 으로 매우 빠르게 접근이 가능합니다. 그러나 실제로는 해시 함수를 계산하는 데 드는 비용과 해시 충돌 해결에 필요한 추가 연산이 필요하기 때문에 연산 시간이 길어질 수 있습니다. 따라서 방문 노드 체크를 위한 자료구조를 배열로 변경했습니다.

정답 코드

struct Queue<T: Comparable> {
    typealias ValueType = (value: T, record: Int)
    
    private var queue: [ValueType] = []
    private var front = 0
    
    var isEmpty: Bool { front >= queue.count }
    
    mutating func enqueue(_ value: ValueType) { queue.append(value) }
    
    mutating func dequeue() -> ValueType? {
        defer {
            front += 1
        }
        return queue[front]
    }
}
let T = Int(readLine()!)!
for _ in 0..<T {
    let ab = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (ab[0], ab[1])
    
    var queue = Queue<Int>()
    queue.enqueue((a, 0))
    var visited: [Bool] = Array(repeating: false, count: 10001)
    visited[a] = true
    
    while !queue.isEmpty {
        let n = queue.dequeue()!
        if n.value == b {
            printResult(n.record)
            break
        }
        
        for op in OperationCode.allCases {
            let next = operate(n: n.value, op: op)
            
            if !visited[next] {
                queue.enqueue((next, n.record * 10 + op.rawValue))
                visited[next] = true
            }
        }
    }
}

enum OperationCode: Int, CaseIterable {
    case D = 1, S, L, R
    
    var toString: String {
        switch self {
        case .D:
            return "D"
        case .S:
            return "S"
        case .L:
            return "L"
        case .R:
            return "R"
        }
    }
}

func printResult(_ record: Int) {
    var record = record
    var result = ""
    
    while record > 0 {
        result += OperationCode(rawValue: record % 10)!.toString
        record /= 10
    }
    print(String(result.reversed()))
}

func operate(n: Int, op: OperationCode) -> Int {
    switch op {
    case .D: // n을 2배
        return n * 2 % 10000
    case .S: // n-1
        return n == 0 ? 9999 : n - 1
    case .L: // n을 왼편으로 회전
        return n % 1000 * 10 + n / 1000
    case .R: // n을 오른편으로 회전
        return n % 10 * 1000 + n / 10
    }
}