[Swift] 프로그래머스 - 단어 변환 (Level. 3)

문제 링크 :https://school.programmers.co.kr/learn/courses/30/lessons/43163 

프로그래머스

 

DFS + 백트래킹 풀이

이 문제가 백트래킹인 근거를 먼저 찾아보자.

1) 순차적으로 알파벳 1개만 바꿔서 target 까지 가야하므로, 단계를 거칠 때마다 가지치기를 통해 경우의 수가 나뉨

2) 경우의 수를 나눌 때 이미 한번 판단한 word는 다시 판단하지 않아야하므로, 방문 여부를 체크할 visited 배열이 필요함

 

import Foundation

func isValidComparision(_ word1: String, _ word2: String) -> Bool { 
    // 1개의 알파벳만 바꿀수 있는가를 판단하는 함수

    var differentCount = 0

    for i in 0..<word1.count{
        if word1[i] != word2[i]{
            differentCount += 1
        }    
    }

    return differentCount == 1 ? true : false
}

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    if !(words.contains(target)){ // target이 words에 없으면 바로 0 return
        return 0
    }
    
    var answer = Int(1e9)
    var visited = Array(repeating: false, count: words.count)
    
    func dfs(_ candidate: String, _ count: Int){
        if candidate == target { // candidate가 target과 같으면 이 때 최소값 비교
            answer = min(answer, count)
            return
        }

        for i in 0..<words.count {
            if visited[i] { continue } // 방문했으면 그 다음 단계 실행
            
            if isValidComparision(candidate, words[i]) {
                visited[i] = true
                dfs(words[i], count+1)
                visited[i] = false
            }
        }
    }
    
    dfs(begin, 0)
    
    return answer 
}

extension String {
    subscript (_ index: Int) -> Character {
        return self[self.index(self.startIndex, offsetBy: index)]
    }
}

 

찾아보니, BFS로도 풀 수 있는 것으로 보여서 이해를 위해 BFS로 다시 풀어보았다.

 

BFS + 백트래킹 풀이

import Foundation

func isValidComparision(_ word1: String, _ word2: String) -> Bool { 
    // 1개의 알파벳만 바꿀수 있는가를 판단하는 함수

    var differentCount = 0

    for i in 0..<word1.count{
        if word1[i] != word2[i]{
            differentCount += 1
        }    
    }

    return differentCount == 1 ? true : false
}

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    if !(words.contains(target)){ // target이 words에 없으면 바로 0 return
        return 0
    }
    
    var answer = Int(1e9)
    var visited = Array(repeating: false, count: words.count)
    
    // BFS 풀이
    func bfs(_ begin: String) {
        var q = [(begin, 0)] // 맨 처음에 step이 0이니까
        
        while !q.isEmpty {
            let (word, c) = q.removeFirst()
            
            if word == target { // 뽑은 수가 target과 같으면 해당 수 answer에 대입 후 종료
                answer = c
                break
            }
            
            for i in 0..<words.count {
                if visited[i] { continue }
                
                if isValidComparision(word, words[i]) {
                    visited[i] = true  // 방문처리
                    q.append((words[i], c + 1)) // 그 다음 탐색 후보지로 word와 단게 추가
                }
            }
        }
    }
    
    bfs(begin)
    
    return answer
}

extension String {
    subscript (_ index: Int) -> Character {
        return self[self.index(self.startIndex, offsetBy: index)]
    }
}