[알고리즘/Swift] 12851 숨바꼭질 2

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 12851 숨바꼭질 2
• 제출 언어: Swift
• 알고리즘 분류:
  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색

---

풀이

이전 문제인 A->B와 유사한 방식으로 풀었으나, 시간초과가 발생하였다.
그 이유는 removeFirst() 함수가 시간복잡도 O(N)의 함수였기 때문에 주어진 시간에 문제를 풀 수 없었다.
그래서 Swift에서의 queue를 구현해서 이 문제를 풀었다

• queue에 수빈이의 위치와 depth를 넣고,
• queue에서 하나의 값을 꺼낼 때마다 -1, +1 x2한 값을 순간이동할 수 있는 위치이고 방문하지 않았을 경우 queue에 넣어주었다
• visited 배열을 두지 않으면 방문한 곳을 계속 queue에 넣어 메모리를 낭비하고, 무한 루프를 돌게 되므로 설정해주었다
• queue에서 값을 꺼냈을 때 동생의 위치와 같아지면
  • 처음 동생을 만난 경우는 해당 depth를 minDepth로 놓고 minDepth를 출력한다, count += 1
  • 처음이 아닐 경우, 해당 depth가 minDepth와 같은 경우 count += 1
• findSister 함수를 마친 후 count 값을 출력한다

전체 코드

class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var visited = Array(repeating: false, count: 100001)
var count = 0
var minDepth = 100001

//방문하지 않았고, 순간이동할 수 있는 위치인지 확인
func isVisitedPossible(_ x: Int) -> Bool {
    if ((0...100000) ~= x) && !visited[x] {
        return true
    }
    else{
        return false
    }
}
func findSister(_ startX: Int) {
    // 수빈이 위치 queue에 넣고 visited true로 초기화.
    let queue = Dequeue([(startX, 0)])
    visited[startX] = true
    
    while !queue.isEmpty {
        let (num, depth) = queue.popFirst()
        // 큐에서 pop할 때 방문처리
        visited[num] = true
        
        // 동생을 찾은 경우
        if num == K {
            // 처음 동생을 찾은 경우
            if count == 0 {
                minDepth = depth
                print(minDepth)
                count += 1
            }
            else {
                // 같은 가장 빠른 시간 내에 또 다른 동생을 찾는 방법
                if minDepth == depth {
                    count += 1
                }
            }
        }
        
        if isVisitedPossible(num+1) {
            queue.pushLast((num+1, depth+1))
        }
        if isVisitedPossible(num-1) {
            queue.pushLast((num-1, depth+1))
        }
        if isVisitedPossible(num*2) {
            queue.pushLast((num*2, depth+1))
        }
    }
}

findSister(N)
print(count)