[programmers/Swift] 단어 변환

programmers.co.kr - 코딩테스트연습 - Lv.2 - 깊이/너비 우선 탐색(DFS/BFS) - 단어 변환

Constraints :

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

Solution.swift :

//
//  Created by Yongwoo Marco on 2022/08/12.
//  Copyright © 2022 Yongwoo Marco Kim. All rights reserved.
//

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
	guard words.contains(target) else { return 0 }
	var result = [Int]()
	
	func dfs(now: String, words: [String], depth: Int, target: String) {
		guard now != target else {
			result.append(depth)
			return
		}
		
		for word in words {
			if (0..<word.count).filter({ Array(now)[$0] == Array(word)[$0] }).count == word.count - 1 {
				dfs(now: word, words: words.filter({ $0 != word }), depth: depth + 1, target: target)
			}
		}
	}
	
	dfs(now: begin, words: words, depth: 0, target: target)
	
	return result.min() ?? 0
}

print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))

How I tried this :
DFS 로 현재 단어와 words의 모든 단어로 다시 dfs를 출발시키는 형태로 depth를 모으고 최소값을 반환함

문제에 관한 모든 저작권 : https://programmers.co.kr/