백준 1963 소수경로, BFS swift 알고리즘 문제 풀이

 

 

안녕하세요 ^-^// 👨🏻‍💻
오늘 다룰 백준 알고리즘 문제는 1963번, 소수경로입니다!
바로 문제 설명을 보겠습니다. 

 

---

1963 - 소수 경로

1963번: 소수 경로

소수경로 문제는 골드5로 책정되어있습니다. 골드5 정도의 문제는 보통 테스트에서 중후반에 나올 가능성이 높다고 볼 수 있습니다. 

 

 

소수경로 문제 네자리의 숫자 2개가 한 줄에 주어졌을때 첫번째 숫자가 두번째 숫자로 변할 수 있는 최소횟수를 구하는 문제인데요. 이 두개의 숫자는 소수입니다. 또한 변화하는 과정에서 숫자는 하나씩 바뀔 수 있으며, 바뀌는 과정의 중간 숫자 들도 모두 소수를 유지해야합니다. 

 

 

해당 문제는 다수의 테스트케이스가 있을 수 있습니다. 각 케이스에는 한줄 입력으로 두개의 소수가 들어옵니다. 
해당 문제는 변화하는 과정에서 1000 미만의 숫자가 나올 수 없습니다. 즉, 변화하는 과정에서의 숫자는 1000 ~ 9999의 범위를 갖습니다.

 특정 영역의 소수를 구하는 좋은 방법이 있죠, 에라토스테네스의 체를 활용해서 소수를 구하고, BFS를 통해 첫번째 소수가 두번째 소수로 변화하는 최소횟수를 구할 수 있습니다. 이때, Int형 ~ String형 간의 형변환을 적절히 처리하며 구현해야 문제를 해결할 수 있습니다. 그렇다면 지금부터 swift로 소수경로 문제를 풀어보겠습니다. 👨🏻‍💻

 

 

---

Swift 문제 풀이

typealias SIPair = (String, Int)
let T = Int(readLine()!)!
let MX = 10001
var PV = [Bool](repeating: true, count: MX+1)
var SV = [Int]()
var EV = [Int]()
PV[0] = false
PV[1] = false

이번 문제는 BFS로 풀수있었다고 했었는데요. 어떤 변수, 배열이 준비되는지 보겠습니다.
- SIPair : 큐에 들어갈 요소 타입을 SIPair로 정의했습니다. (현재 문자열값, 변경횟수) 를 (String, Int) 타입으로 받을 수 있도록 합니다. 
- MX : 다뤄질 소수의 범위는 1000 ~ 9999라고 했었죠? 그래서 최댓값 범위로 안전하게 MX값으로 10001을 정해두었습니다. 
- PV : PV는 각 소수를 인덱스와 대응해서 소수여부를 체크하는데 사용합니다. 
- SV : 시작하는 소수의 각 자리 숫자를 다루기 위해 Int형 배열을 사용합니다.
- EV : 최종적으로 변해야 하는 소수의 각 자리 숫자를 다루기 위해 Int형 배열을 사용합니다. 
- PV : 0, 1은 소수가 아니므로 미리 false로 소수 아님 처리를 해둡니다. 

 

 

var i = 2, j = 4
while i*i <= MX {
  if PV[i] {
    j = i+i 
    while j <= MX {
      PV[j] = false
      j += i
    }
  }
  i += 1
}

위의 코드는 어떤 코드인지 예상이 가시나요? 바로 위의 코드는 swift의 에라토스테네스의 체 활용 예시입니다. 
swift는 에라토스테네스의 체르 구현할 때 다소 불편한 점이 있습니다. for 문을 사용하게 되면 다소 세부적인 조건에 따라 증감연산을 해야하는 이유로 제한이 있고, stride 반복문을 통해 연산할 수 있지만, 정수형 연산과는 목적성이 다소 차이가 있습니다. 

그래서 while문을 통해서 정수형을 유지하면서 에라토스테네스의 체를 구현했습니다. 에라토스테네스의 체의 시간복잡도는 NloglogN으로 매우 효율적인 알고리즘입니다. 특정 영역의 전체 소수를 구할 때 탁월합니다. 

이렇게 PV 배열에는 ~ 10001 까지의 범위 중 소수의 값을 구할 수 있게 됩니다. 👍🏼

에라토스테네스의 체 관련 링크 ▼

에라토스테네스의 체 - 나무위키

 

 

 

extension Array where Element == Int {
  func convertArrToInt() -> Int {
    return self[0] * 1000 + self[1] * 100 + self[2] * 10 + self[3]
  }

  func convertArrToStr() -> String {
    return "\(self[0])\(self[1])\(self[2])\(self[3])"
  }
}

해당 코드는 이후 BFS 간 네자리 Int배열을 Int값으로, Int배열을 문자열로 변화하는데 사용하는 Array extension 코드 부입니다. swift에서 Array extension을 활용하면 메서드에 직접 배열 인자값을 넘길 필요없이 특정 배열 뒤에 dot '.' 접근만으로 연산을 수행할 수 있어 편리합니다. 

 

 

func BFS() -> Int {
  var Q = [SIPair]()
  // 방문 체크에 사용하는 visit 배열
  var visit = [Bool](repeating: false, count: MX)
  // 큐의 pop 될 위치를 잡고 있는 cur 변수, cur 변수가 Q의 범위를 초과하면 Q가 비었음을 의미합니다. 
  // 기본적으로 스위프트에서는 큐를 지원하지 않기 때문에 대체하여 사용할 수 있는 것이 해당 큐 구현 방식입니다. 
  var cur = 0
  // 처음 시작하는 문자열을 사전에 방문 처리합니다. 
  visit[SV[0]*1000 + SV[1]*100 + SV[2]*10 + SV[3]] = true
  
  // 시작문자열, 최종문자열의 각 자리 숫자를 담는 배열을 준비하여 BFS를 시작합니다. 
  let S = SV.convertArrToStr()
  let E = EV.convertArrToStr()
  Q.append((S, 0))
  
  while cur < Q.count {
  	// 현재 큐의 숫자를 꺼냅니다. 
    let now = Array(Q[cur].0).map { Int(String($0))! }
    // 현재 큐의 문자열 이전까지 변화한 횟수를 꺼냅니다. 
    let cnt = Q[cur].1
    // cur += 1은 Q를 한번 pop 한 것과 같은 효과를 갖습니다. 
    cur += 1
    
    // 각 자리에 대해 0 ~ 9까지 변화를 하며 소수가 성립, 방문하지 않은 소수일 경우 다시 큐에 넣음을 반복하며 BFS를 수행합니다. 
    for i in 0..<4 {
      for j in 0...9 {
        var tNow = now
        tNow[i] = j
        let tNum = tNow.convertArrToInt()
        let tStr = tNow.convertArrToStr()
        // 현재 변화한 숫자가 소수가 아니거나 || 1000이하거나 || 이미방문한적이 있다면 건너뜁니다. 
        if PV[tNum] == false || tNum < 1000 || visit[tNum] == true { continue }
        visit[tNum] = true
        if tStr == E { return cnt + 1 }
        Q.append((tStr, cnt+1))
      }
    }
  }
  return 0
}

가장 핵심적인 코드인 BFS코드부 입니다. 시작 숫자값부터 시작해서 각 자리의 숫자를 0 ~ 9의 값으로 바꿔가며 소수인지, 방문한 소수인지, 1000이하인지를 체크하며 BFS 탐색을 진행합니다.
 이때 BFS 중 소수이고, 1000이상이며 방문한적이 없다면 방문처리 후 해당 값은 큐에 (바뀐 소수값, 현재까지 바뀐 값 + 1) SIPair 값으로 넣어줍니다. 이를 반복해서 변화한 값이 최종 소수값이라면 현재까지 바뀐값 + 1을 결과값으로 반환하여 값을 도출합니다. 

 

for _ in 0..<T {
  let arr = readLine()!.split(separator: " ")
  SV = Array(arr[0]).map { Int(String($0))! }
  EV = Array(arr[1]).map { Int(String($0))! }
  print(BFS())
}

앞서 구현했던 BFS코드의 실행 및 반환값을 출력하는 코드입니다.
이렇게 소수경로문제는 에라토스테네스의체 + BFS를 통해 소수경로 문제를 해결해볼 수 있었습니다. 🤗

많은 의견 환경합니다. 즐거운 하루 되세요 ^-^ 👨🏻‍💻

 

 

 

 

---

Swift Algorithm Club 커뮤니티 방 링크 ▼

Swift Algorithm Club