백준 9019번 DSLR (swift) [G5]

BFS(깊이 우선 탐색)

생각회로

• DP 였다면, '어떤 방식이 답에 가까운 식인가'가 명확해야 한다고 생각했다.
• 답을 구할 때 까지, 모든 경우를 생각해야 한다고 생각했다. -> BFS or DFS
• DFS 로 구현하면, DDDDD만 반복하다가 시간 다 잡아먹을 것 같다 -> BFS
• BFS 답게 큐를 구현했고, A의 값을 큐에 넣고, 답을 찾을 때 까지 반복했다.
• visit[10001] 배열로, 방문한 값 재 방문 방지와 동시에, 그 값을 만드는데 사용한 연산(DSLR)을 저장했다.
• 연산은 답과 마찬가지로 "DDDD" 와 같이 String 으로 처리하려고 했으나... 시간초과 발생

주의사항

• 결과적으로 visit 배열에 String 을 저장하고, append 하는 연산에서 시간초과를 유발했다.

• String 의 append도 O(1) 이지만, (String의 처리 시간 + overflow 발생시 복사 O(n)) 등의 시간이 시간초과를 발생한 것 같다. -> 효율적이게 정수로 변환
• D(A) 등 함수를 3번 호출 하는 것도, 시간을 줄이기위해 DD 변수로 한번 호출하게 했다.
• 함수의 return을 생략해도 되서 기분이 좋다.

import Foundation

class queue{
    var enq = [Int]()
    var deq = [Int]()
    
    var count: Int{
        return enq.count + deq.count
    }
    
    func push(_ a:Int){
        enq.append(a)
    }
    
    func pop()->Int{
        if deq.count == 0{
            deq = enq.reversed()
            enq.removeAll()
        }
        if deq.count == 0{
            return -1
        }
        return deq.popLast()!
    }
}

func D(_ A:Int)->Int{
    (A * 2) % 10000
}

func S(_ A:Int)->Int{
    A != 0 ? A - 1 : 9999
}

func L(_ A:Int)->Int{
    (A * 10)%10_000 + (A/1000)
}

func R(_ A:Int)->Int{
    (A/10) + (A%10)*1000
}

let T = Int(readLine()!)!


for _ in 0..<T{
    var visit = Array<Int?>(repeating: nil, count: 10001)
    let input = readLine()!.split(separator: " ").map{Int($0)!}
    var A = input[0]
    let B = input[1]
    let q = queue()
    
    q.push(A)
    visit[A] = 0
    while q.count != 0 {
        A = q.pop()
        let DD = D(A)
        let SS = S(A)
        let LL = L(A)
        let RR = R(A)
        
        if A == B{
            break
        }
        if visit[DD] == nil{
            q.push(DD)
            visit[DD] = visit[A]! * 10 + 1
//          visit[DD] = visit[A] + "D"  ->이전 방식
        }
            
        if visit[SS] == nil{
            q.push(SS)
            visit[SS] = visit[A]! * 10 + 2
        }
        if  visit[LL] == nil{
            q.push(LL)
            visit[LL] = visit[A]! * 10 + 3
        }
        if  visit[RR] == nil{
            q.push(RR)
            visit[RR] = visit[A]! * 10 + 4
        }
    }
    
    var ans = String(visit[B]!)

    for i in ans{
        switch i{
        case "1": print("D",terminator: "")
        case "2": print("S",terminator: "")
        case "3": print("L",terminator: "")
        case "4": print("R",terminator: "")
        default:
            break;
        }
    }
    print()
}