[Algorithm] 단어 변환

[hwangJi-dev]

💬 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43163

💬 Idea

[첫번째 아이디어]

• words를 돌면서 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 라는 조건에 부합하는 words 트리를 만든다.
• ex: [”hit”: [”hot”], “hot”: [”dot”, “lot”], “dot”: [”dog”], “lot”: [”log”], “dog”: [”log”, “cog”], “log”: “[”dog”, “cog”]]
• 이후 시작 단어인 begin부터 dfs 작업을 수행하며 방문한 노드가 적은 경우라면 minChangeCnt를 갱신해주었다.
  • 재귀함수 종료 조건: word == target

💬 풀이1

import Foundation

var minChangeCnt = 0

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
 if !words.contains(target) { return 0 }
 
 let words = [begin] + words
 var changableDict: [String: [String]] = [:]
 
 for i in words {
 let i = String(i)
 if changableDict[i] == nil {
 changableDict[i] = []
 }
 
 for j in words {
 if j == i { continue }
 
 if isChangableWord(i, j) {
 changableDict[i]?.append(j)
 }
 }
 }
 
 dfsToFindTargetWord(begin, target, [], changableDict)
 
 return minChangeCnt
}

func isChangableWord(_ word1: String, _ word2: String) -> Bool {
 let word1 = Array(word1)
 let word2 = Array(word2)
 
 var diff = 0
 for i in 0..<word1.count {
 if word1[i] != word2[i] {
 diff += 1
 }
 }
 
 return diff == 1 ? true : false
}

func dfsToFindTargetWord(_ word: String, _ target: String, _ visited: [String], _ dict: [String: [String]]) {
 var visited = visited
 
 if word == target {
 minChangeCnt = minChangeCnt == 0 ? visited.count : min(visited.count, minChangeCnt)
 return
 }
 
 guard let _ = dict[word] else { return }
 
 if dict[word]!.isEmpty {
 return
 } else {
 visited.append(word)
 for i in dict[word]! {
 if !visited.contains(i) {
 dfsToFindTargetWord(i, target, visited, dict)
 }
 }
 }
}

💬 Idea

[두번째 아이디어]

• 트리를 만들지 않고 방문처리를 통해서만 dfs를 수행해준다.
• 재귀함수 종료 조건: word == target
• words를 돌면서
  • 해당 노드를 방문하지 않았고, 해당 노드가 시작 word와 한 개의 알파벳만이 다른 경우라면
    • 방문처리를 해준 후
    • word를 해당 노드로 변경하고 depth + 1을 하여 dfs를 수행한다.
  • dfs 수행 이후에 다른 경로로는 해당 노드를 다시 방문할 수 있도록 하기 위해 해당 노드의 visited 상태를 false로 변경해준다.

💬 풀이2

import Foundation

var minChangeCnt = 0

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
 if !words.contains(target) { return 0 }
 var visited = Array(repeating: false, count: words.count)
 dfsToFindTargetWord(words, begin, target, 0, &visited)
 return minChangeCnt
}

func isChangableWord(_ word1: String, _ word2: String) -> Bool {
 let word1 = Array(word1)
 let word2 = Array(word2)
 
 var diff = 0
 for i in 0..<word1.count {
 if word1[i] != word2[i] {
 diff += 1
 }
 }
 
 return diff == 1 ? true : false
}

func dfsToFindTargetWord(_ words: [String], _ word: String, _ target: String, _ depth: Int, _ visited: inout [Bool]) {
 if word == target {
 minChangeCnt = minChangeCnt == 0 ? depth : min(depth, minChangeCnt)
 return
 }
 
 for (idx, i) in words.enumerated() {
 if visited[idx] == false && isChangableWord(word, i) {
 visited[idx] = true
 dfsToFindTargetWord(words, i, target, depth + 1, &visited)
 visited[idx] = false
 }
 }
}

2번째 풀이가 훨씬 좋은 효율성을 가지는 것을 확인할 수 있다 😊