[Algorithm] 백준 - 9019번 DSLR (Swift) (시간초과)

문제 소개

문제 자체는 간단하다. DSLR 연산을 통해 a에서 b까지 최소한의 명령어 나열을 출력하는 문제이다.

 

문제 풀이

이 문제는 푸는데는 시간이 많이 걸리지 않았지만 시간 초과로 애를 먹었다. 시간제한이 6초인데 겨우 5880ms 로 통과했다... 다시해봐도 5824ms 가 나오는 것을 봐서는 맞긴 맞은 모양이다...

눈물겨운 흔적들...

 

정답 코드

dslr 함수를 구현하고, bfs를 활용했다. L과 R연산을 문자배열을 만들어 하게되면 무조건 시간 초과가 나오게 되어서 연산으로만 구현해줘야 한다. 그리고 처음에는 queue 에 (num, command) 로 넣어주니 이것도 시간초과가 나왔다. 그래서 따로 commands 배열을 만들어 관리해주니 시간 단축이 되었다. queue도 removeFirst() 를 사용하지 않고 idx를 사용하여 관리해주었다. 물론 queue에서 pop을 해주지 않고 단순히 index로 관리해주면 메모리 문제가 있지만 여기서는 최대 10000개가 쌓이기 때문에 문제 없다고 생각했다.

import Foundation

let t = Int(readLine()!)!
let calc = ["D", "S", "L", "R"]

func dslr(_ num: Int, _ command: String) -> Int {
    switch command {
    case "D": return (num * 2) % 10000
    case "S": return num - 1 < 0 ? 9999 : num - 1
    case "L": return (num % 1000) * 10 + (num / 1000)
    case "R": return num / 10 + num % 10 * 1000
    default: return 0
    }
}

for _ in 0..<t {
    let ab = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (ab[0], ab[1])
    
    var queue = [a]
    var idx = 0
    var visited = Array(repeating: false, count: 10000)
    var commands = Array(repeating: "", count: 10000)
    visited[a] = true
    
    while queue.count > idx {
        let poped = queue[idx]
        idx += 1
                
        if poped == b {
            print(commands[b])
            break
        }
        
        for cal in calc {
            let next = dslr(poped, cal)
            if !visited[next] {
                visited[next] = true
                commands[next] = commands[poped] + cal
                queue.append((next))
            }
        }
    }
}