백준 1039 - 교환 - swift

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

1039번: 교환

 

완전탐색이 필요한 문제다. 

 

완전탐색을 하면 중복되는 경우의수가 존재할수있는데, 

이는 check [ 숫자 ] [ k ]  = k번 교환했을때 숫자가 이미 나왔는지 

로 체크하여 중복횟수를 줄일 수 있다. 

 

길이가 1인경우와  길이가 2면서 0이포함된 숫자는 교환할수없다는 부분도 고려해야한다. 

 

let inp = readLine()!.split(separator: " ").map{Int(String($0))!}
var check = Array(repeating: Array(repeating:false, count:11), count: 1000001)
let len = String(inp[0]).count
var mx = 0
var queue = [(String(inp[0]).map{String($0)}, 0)]
var q = 0

while queue.count > q {
    let f = queue[q]
    q += 1
    if f.1 == inp[1] {
        mx = max(mx, Int(f.0.joined())!)
        continue
    }
    for i in 0..<len {
        for j in i+1..<len {
            var tempt = f.0
            tempt.swapAt(i,j)
            if tempt[0] == "0" { continue }
            let x = Int(tempt.joined())!
            if check[x][f.1+1] { continue }
            check[x][f.1+1] = true
            queue.append((tempt, f.1+1))
        }
    }
}
print(mx == 0 ? -1 : mx)