백준 9019번 DSLR - 스위프트(Swift) 시간초과 해결

 BFS를 돌면서 해당 노드까지 오게 된 경로를 기록해야 하는데, 바로 출력 가능하도록 이전 노드까지 오게 된 경로 문자열에 + 연산자를 사용해서 기록을 하니 시간 초과가 났다. 문자열에 +하는 연산은 역시 코스트가 엄청 큰가 보다.

  n을 2배로 만드는 D 연산이 있기 때문에 최대 연산 횟수가 logN 언저리일 것이므로 Int의 각 자릿수에 한 글자가 대응되도록 저장이 가능했다. "D", "S", "L", "R"을 각각 1, 2, 3, 4로 대응시켜 122314 = "DSSLDR"처럼 읽을 수 있도록 기록했더니 통과되었다. 마지막에 출력할 때 숫자 → 문자열로 변환하는 작업을 한번 거쳐줘야 한다.

---

import Foundation

struct Queue {
    var queue = [Int]()
    var front = 0
    
    var isEmpty: Bool {
        return front >= queue.count
    }
    
    mutating func insert(_ n: Int) {
        queue.append(n)
    }
    
    mutating func popFront() -> Int {
        let ret = queue[front]
        front += 1
        return ret
    }
}

func toCommand(_ n: Int64) -> String {
    var ret = ""
    var x = n
    
    let dict = ["", "D", "S", "L", "R"]
    
    while x > 0 {
        ret += dict[Int(x % 10)]
        x /= 10
    }
    
    return String(ret.reversed())
}

func BFS(start: Int, target: Int) -> String {
    var queue = Queue()
    var visit = Array(repeating: false, count: 10000)
    var path = Array(repeating: Int64(0), count: 10000)     // String이 아니라 Int로 기록
    
    queue.insert(start)
    visit[start] = true
    
    while !queue.isEmpty {
        let n = queue.popFront()
        
        if n == target { return toCommand(path[n]) }
        
        let D = 2 * n % 10000
        let S = n == 0 ? 9999 : n - 1
        let L = n % 1000 * 10 + n / 1000
        let R = n / 10 + n % 10 * 1000
        
        let adjacents = [(D, 1), (S, 2), (L, 3), (R, 4)]
        for adj in adjacents {
            let next = adj.0
            let cmd = adj.1
            
            if !visit[next] {
                visit[next] = true
                path[next] = path[n] * 10 + Int64(cmd)
                queue.insert(next)
            }
        }
    }
    
    return "-1"
}

func solution() -> String {
    var result = ""
    var T = Int(readLine()!)!
    
    while T > 0 {
        let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        let A = input[0]
        let B = input[1]
        
        result.write(BFS(start: A, target: B) + "\n")
        
        T -= 1
    }
    
    return result
}

print(solution())