1697. 숨바꼭질

[zekexros]

https://www.acmicpc.net/problem/1697

[zekexros]

https://github.com/zeke-iOS/AlgorithmPractice/blob/main/BOJ/BOJ-1697(숨바꼭질).swift

[lenaios]

why timeout...😥

import Foundation

var memo = Set<Int>()
func bfs(_ target: Int, _ arr: [Int], _ depth: Int) -> Int {
    if arr.contains(target) {
        return depth
    }

    var next: [Int] = []
    arr.forEach {
        if !memo.contains($0 - 1) {
            next.append($0 - 1)
        }
        if !memo.contains($0 + 1) {
            next.append($0 + 1)
        }
        if !memo.contains($0 * 2) {
            next.append($0 * 2)
        }
        memo.insert($0 - 1)
        memo.insert($0 + 1)
        if $0 * 2 < 100000 { memo.insert($0 * 2) }
    }
    return bfs(target, next, depth + 1)
}

let input = readLine()!.components(separatedBy: " ")
let start = Int(input[0])!
let end = Int(input[1])!
let ans = bfs(end, [start], 0)
print(ans)

[ghis22130]

https://ghis22130.github.io/2021-07-28-%EB%B0%B1%EC%A4%80_%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88(1697)/