[프로그래머스] 단어 변환

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

프로그래머스

 

접근

---

• 목표에 도달할 때까지의 최소 단계를 찾는 것이 목표이기 때문에, DFS 또는 BFS 알고리즘 사용

 

로직

---

• answer로 최소 단계의 과정을 저장하고, 값 초기화는 정수의 최댓값으로 설정
• dfs 메서드 안에서 words에 대해 반복문을 수행. 현재 단어와 알파벳이 하나만 다른 단어를 찾는다
• visit을 통해 현재 점검해야 하는 단어를 이미 지나왔는지 확인하여 이미 지나온 경우, 점검하지 않고 넘어간다
• 빠른 종료를 위해 현재 진행 중인 루트의 depth가 answer 보다 크거나 같다면 종료한다

 

코드

---

1. Python 

def solution(begin, target, words):
    
    maxSize = 2**63-1
    
    def isValid(a, b):
        
        a = list(a)
        b = list(b)
        
        diff = 0
        for i in range(len(a)):
            if a[i] != b[i]:
                diff += 1
            if diff > 1 :
                return False
        return True
    
    global answer 
    answer = maxSize
    
    global visit
    visit = [False] * len(words)
    
    def dfs(w, depth):
        
        if w == target:
            global answer
            answer = min(answer, depth)
            return 
        if depth >= answer:
            return 
        
        for (i, temp) in enumerate(words):
            global visit
            if visit[i]: 
                continue
            if isValid(temp, w):
                visit[i] = True
                dfs(temp, depth+1)
                visit[i] = False
    
    dfs(begin, 0)
    
    if answer == maxSize:
        return 0
    return answer

 

2. Swift

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    
    var answer = Int.max
    var visit = [Bool](repeating: false, count: words.count)
    
    func isValid(_ a: String, _ b: String) -> Bool {
        let a = Array(a)
        let b = Array(b)
        var diff = 0
        for i in 0..<a.count {
            if a[i] != b[i] {
                diff += 1
            }
            if diff > 1 {
                return false
            }
        }
        return true
    }
    
    func dfs(_ w: String, _ depth: Int) {
        if target == w {
            answer = min(answer, depth)
            return
        }
        if depth >= answer {
            return
        }
        for (i, temp) in words.enumerated() {
            if visit[i] { continue }
            if isValid(temp, w) {
                visit[i] = true
                dfs(temp, depth + 1)
                visit[i] = false
            }
        }
    }
    
    dfs(begin, 0)
    
    if answer == Int.max {
        return 0
    }
    return answer
}