[1525] 퍼즐

var start = [String]()
for _ in 0..<3 {
    start += readLine()!.split(separator: " ").map{String($0)}
}
var visited = Set<String>()
var q = [(start, 0)]
var index = 0
let answer = (1...8).map{String($0)} + ["0"]
let dx = [1, 3, -1, -3]
var isPossible = false

while index < q.count {
    var num = q[index].0
    let cnt = q[index].1
    let x = num.firstIndex(of: "0")!
    visited.insert(num.joined())
    index += 1
    
    if num == answer {
        isPossible = true
        print(cnt)
        break
    }

    for i in 0..<4 {
        let nx = x + dx[i]
        if x % 3 == 0, i == 2 { continue }  // 가로 1에서 가로 3으로 이동 불가
        if x % 3 == 2, i == 0 { continue }  // 가로 3에서 가로 1로는 이동 불가
       
        if 0 <= nx, nx < 9 {
            num.swapAt(nx, x)
            if !visited.contains(num.joined()) {
                visited.insert(num.joined())
                q.append((num, cnt+1))
            }
            num.swapAt(nx, x)
        }
    }
}
if !isPossible { print(-1) }