[Swift][BFS] 백준 1963번 (소수 경로)

요구능력 : BFS && 에라토스테네스의 체

 

코드설명 : 

 

이 문제의 핵심

1) 비밀번호를 한 번에 한자리 밖에 못바꾼다.

2) 1000이상 9999이하의 범위만 가능하다.

3) 소수로만 단계를 거쳐야한다.

 

두 소수 사이의 변환에 필요한 최소 회수를 출력한다고 했으므로, BFS를 의심해본다.

 

1) 비밀번호를 한 번에 한자리 밖에 못바꾼다.

이 조건이 이 문제의 핵심인데,

비밀번호를 한 번에 한자리 바꾼다고 했으므로, 입력받은 수가 있으면 천의자리를 바꿔서 큐에넣고, 백의자리를 바꿔서 큐에넣고, 십의자리를 바꿔서 큐에넣고, 일의자리를 바꿔서 큐에넣는다. 이렇게 BFS로 풀어주면 된다는 생각이 들었다.

 

처음 큐에 입력받은 숫자를 넣은 뒤, 그 숫자의 천의자리, 백의자리, 십의자리, 일의자리를 추출해서 배열에 넣어주고

큐를 한번 pop했을 때, for문을 이용해서 0~9까지의 수를 천의자리, 백의자리, 십의자리, 일의자리에 각각 넣어보고 

위에서 말한 2번 3번조건이 맞을경우에는 큐에 추가해주고 방문한다.

이렇게 추가해주고나면 다음번의 자리수를 돌기위해서 원래대로 되돌려 놓는다.

 

3번조건의 경우 에라토스테네스의 체를 이용해서 문제를 풀었는데, 구글에 에라토스테네스의 체를 검색하면 동빈나님께서 엄청 이해 잘가게 정리를 해두셨으니 참고하기를 바랍니다.

 

후기 : BFS라는것을 알고 풀었기에 쉬웠던거같다.

몰랐으면 조금 헤맸을 수도 있을것같다.

let t = Int(String(readLine()!))!
var tostenes = Array(repeating: 1, count: 10001)
for i in 2..<10001{
    tostenes[i] = i
}
for i in 2..<10001{
    if tostenes[i] == 0 {continue}
    for j in stride(from: i + i, to: 10001, by: i){
        tostenes[j] = 0
    }
}

for _ in 0..<t{
    let two = readLine()!.split(separator: " ").map{Int(String($0))!}
    let a = two[0]
    let b = two[1]
    
    bfs(a, b)
}


func bfs(_ a: Int, _ b: Int){
    var visited = Array(repeating: false, count: 10000)
    var queue = [(Int, Int)]()
    queue.append((a, 0))
    visited[a] = true
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        
        if pop.0 == b {
            print(pop.1)
            break
        }
        var n = pop.0
        
        let sausands = n / 1000
        n = n % 1000
        let hundreds = n / 100
        n = n % 100
        let ten = n / 10
        n = n % 10
        let one = n
        
        var arr = [sausands, hundreds, ten, one]

        for i in 0...9{
            for j in 0..<4{
                let temp = arr[j]
                arr[j] = i
                let total = arr[0] * 1000 + arr[1] * 100 + arr[2] * 10 + arr[3]
                if total >= 1000 && total <= 9999 && tostenes[total] != 0 && !visited[total]{
                    queue.append((total, pop.1 + 1))
                    visited[total] = true
                }
                arr[j] = temp //원래대로 되돌려놓기
                
            }
            
            
        }
        
    }
}