[Swift] 단어 변환 문제 풀이 [Programmers - Level3 (DFS/BFS)]

💬 문제

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
}

/// ⚙️ 2가지 단어간 변환이 가능한지 검사(확인)하는 메서드
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
}

/// ⚙️ dfs로 target 단어를 찾는 메서드
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)
            }
        }
    }
}

어찌어찌 맞긴 했지만,, 효율성이 좋지 않은 것 같아서 고민을 하다가, 더 좋은 풀이 아이디어가 떠올라 2차 풀이를 시작했습니다 !

 

---

💬 Idea2

[두번째 아이디어]

• 트리를 만들지 않고 방문처리를 통해서만 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
}

/// ⚙️ 2가지 단어간 변환이 가능한지 검사(확인)하는 메서드
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
}

/// ⚙️ dfs로 target 단어를 찾는 메서드
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
        }
    }
}

 

 

첫번째 풀이는 그래프를 만들기 위해 O(N^2)의 탐색과정을 거치고, 또 해당 그래프를 dfs를 통해 탐색하기 때문에 효율성이 좋지 않았는데요,

두번째 풀이에서 그래프를 만들기 위한 불필요한 탐색과정을 줄이니 훨씬 좋은 효율성을 가지는 것을 확인할 수 있었습니다 😊

 

 

 

 

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Programmers/level3/%EB%8B%A8%EC%96%B4%20%EB%B3%80%ED%99%98.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift