백준 13549 숨바꼭질 3

출처: www.acmicpc.net/problem/13549

분류: BFS, Deque

---

접근방식

현재 위치에서 이동할 수 있는 위치를 담으면서 BFS 탐색을 해서 해결할 수 있습니다.

단, 그냥 앞뒤 이동 보다 jump가 비용이 더 적게 들기 때문에 jump를 우선적으로 처리해줘야 합니다.

이때 사용할 수 있는 방법은 여러가지인 것 같은데요, 

저는 jump는 queue의 앞에 추가하고 나머지는 뒤에 추가하는 방식으로 jump를 우선적으로 처리해줬습니다.

시간은 널널해서 그냥 배열로도 처리할 수 있는데, deque를 사용하면 효율을 훨씬 높일 수 있습니다.

 

해결방법

그냥 배열

let nk = readLine()!.split(separator: " ").map { Int(String($0))! }

var values = [Int](repeating: 100000, count: 100001)
values[nk[0]] = 0
var visit = [Bool](repeating: false, count: 100001)
var queue = [nk[0]]

while !queue.isEmpty {
    let curr = queue.removeFirst()

    guard curr != nk[1] else {
        print(values[nk[1]]); break
    }
    
    if curr * 2 <= 100000, !visit[curr*2] {
        queue.insert(curr*2, at: 0)
        values[curr*2] = values[curr]
        visit[curr*2] = true
    }
    if curr+1 <= 100000, !visit[curr+1] {
        queue.append(curr+1)
        values[curr+1] = values[curr]+1
        visit[curr+1] = true
    }
    if curr-1 >= 0, !visit[curr-1] {
        queue.append(curr-1)
        values[curr-1] = values[curr]+1
        visit[curr-1] = true
    }
}

deque

public struct Deque<T> {
  private var array: [T?]
  private var head: Int
  private var capacity: Int
  private let originalCapacity: Int

  public init(_ capacity: Int = 10) {
    self.capacity = max(capacity, 1)
    originalCapacity = self.capacity
    array = [T?](repeating: nil, count: capacity)
    head = capacity
  }

  public var isEmpty: Bool {
    return count == 0
  }

  public var count: Int {
    return array.count - head
  }

  public mutating func enqueue(_ element: T) {
    array.append(element)
  }

  public mutating func enqueueFront(_ element: T) {
    if head == 0 {
      capacity *= 2
      let emptySpace = [T?](repeating: nil, count: capacity)
      array.insert(contentsOf: emptySpace, at: 0)
      head = capacity
    }

    head -= 1
    array[head] = element
  }

  public mutating func dequeue() -> T? {
    guard head < array.count, let element = array[head] else { return nil }

    array[head] = nil
    head += 1

    if capacity >= originalCapacity && head >= capacity*2 {
      let amountToRemove = capacity + capacity/2
      array.removeFirst(amountToRemove)
      head -= amountToRemove
      capacity /= 2
    }
    return element
  }

  public mutating func dequeueBack() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeLast()
    }
  }

  public func peekFront() -> T? {
    if isEmpty {
      return nil
    } else {
      return array[head]
    }
  }

  public func peekBack() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.last!
    }
  }
}

let nk = readLine()!.split(separator: " ").map { Int(String($0))! }

var values = [Int](repeating: 100000, count: 100001)
values[nk[0]] = 0
var visit = [Bool](repeating: false, count: 100001)
var deque = Deque<Int>()
deque.enqueue(nk[0])

while !deque.isEmpty {
    let curr = deque.dequeue()!

    guard curr != nk[1] else {
        print(values[nk[1]]); break
    }

    if curr * 2 <= 100000, !visit[curr*2] {
        deque.enqueueFront(curr*2)
        values[curr*2] = values[curr]
        visit[curr*2] = true
    }
    if curr+1 <= 100000, !visit[curr+1] {
        deque.enqueue(curr+1)
        values[curr+1] = values[curr]+1
        visit[curr+1] = true
    }
    if curr-1 >= 0, !visit[curr-1] {
        deque.enqueue(curr-1)
        values[curr-1] = values[curr]+1
        visit[curr-1] = true
    }
}

 

배운점

이런 문제에서 BFS가 아직 낯설다... 

비슷한 유형이 나올 때 풀 수 있게 잘 기억해두자!!!