안녕하세요 : )
https://programmers.co.kr/learn/courses/30/lessons/43163
begin에서 시작해서 target이 될 때까지 단어를 변환하는 최소 횟수를 구하는 문제입니다.
풀이
그냥 Array를 이용해서 BFS로 구현했습니다. 한 개의 알파벳만 다르면 변환할수 있으므로 queue에 넣습니다.
이 때, 이미 확인했는지 check하는 배열을 만들어 체크를 하지 않았다면(false) 넣습니다.
import Foundation
func isChange(_ word: String, _ now: String) -> Bool {
if word.count != now.count {
return false
}
var count: Int = 0
let arrWord = Array(word)
let arrNow = Array(now)
for i in 0..<arrWord.count {
if arrWord[i] != arrNow[i] {
count += 1
}
if count > 1 {
return false
}
}
return true
}
func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
if !words.contains(target) {
return 0
}
var queue: [String] = []
queue.append(begin)
var check = [Bool] (repeating: false, count: words.count)
var count: Int = 0
while !queue.isEmpty {
let now = queue.popLast()!
if now == target {
break
}
count += 1
for idx in 0..<words.count {
if !check[idx] {
if isChange(words[idx], now) {
queue.append(words[idx])
check[idx] = true
}
}
}
}
return count
}
popLast() 쓰신거면 큐를 만드시고 스택으로 사용하신 거 아닌가요?
그렇다면 dfs로 푸신 거 아닌가요?