[백준] BFS - 1697번 숨바꼭질

1697번: 숨바꼭질

입력 & 출력

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 
만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

풀이

트리 형식으로 생각했다. 수빈이의 위치 값을 저장하고 해당 위치에 2배를 곱한 값, +1 값, -1 값 을 구한다.
구한 값을 기준으로 반복해가며 동생 위치에 도달하는 빠른 시간을 찾는다.
탐색한 곳을 재탐색하지 않기 위해 visited를 달았다. 안전한 탐색을 위해 조건문을 달아주자.

Swift 전체 코드

let num = readLine()!.split(separator: " ").map { Int($0)! }
var array : [Int] = [num.first!]
var visited : [Bool] = .init(repeating: false, count:100_001)
var temp : [Int] = []
var count = 0

while num.first! != num.last! {
    let value = array.removeLast()
    
    let mul = value * 2
    let add = value + 1
    let sub = value - 1
    
    if [mul, add, sub].contains(num.last) {
        count += 1
        break
    }
    
    if value < 100_001 && visited[value] == false {
        visited[value] = true
    }
    if sub >= 0 && sub < 100_001 && visited[sub] == false {
        temp.append(sub)
        visited[sub] = true
    }
    if value < num.last!  {
        if add < 100_001 && visited[add] == false {
            temp.append(add)
            visited[add] = true
        }
        if mul < 100_001 && visited[mul] == false {
            temp.append(mul)
            visited[mul] = true
        }
    }
    
    if array.isEmpty {
        array.append(contentsOf: temp)
        temp = []
        count += 1
    }
}

print(count)