Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 단어 변환

[단어 변환]

Solution 1. Backtracking

def solution(begin, target, words):

    def backtracking(cur, cnt=0):
        if cur == target: return cnt

        mn = 11
        for w in words:
            if w not in used and sum(x != y for x, y in zip(cur, w)) == 1:
                used.add(w)
                nxt = backtracking(w, cnt+1)
                mn = min(mn, nxt)
                used.discard(w)
        
        return mn
    
    used = {begin}
    return 0 if (ret:= backtracking(begin)) == 11 else ret

• 단어의 길이는 최대 $10$이므로 최솟값을 일단 11로 초기화한 다음 재귀적으로 갱신한다. 이 최솟값이 갱신되지 않았다는 것은 변환할 수 없다는 것을 의미하므로 0을 return한다.
• 한 번에 한 개의 알파벳만 바꿀 수 있기 때문에, 어떤 단어가 다른 단어로 바뀌기 위해서는 하나의 문자만 달라야 한다. 이 부분을 sum(x != y for x, y in zip(cur, w)) == 1로 구현했다.
• 이미 변환하는 데 이용했던 단어를 다시 이용하는 것은 최소 변환 횟수가 아니다. (A→ B→ C가 아닌 A→B→A→B→C와 같은 경우) 따라서 변환하는 데 이용했던 단어들을 집합으로 관리하면 가지치기에 도움이 된다.

Solution 1-2. Backtracking

def solution(begin, target, words):
    if target not in words: return 0

    def check(a, b):
        cnt = 0
        for x, y in zip(a, b):
            if x != y:
                cnt += 1
                if cnt > 1: return False
        
        return cnt

    def backtracking(cur, cnt=0, mn=11):
        if cur == target: return cnt
        if cnt >= mn: return

        for w in words:
            if w not in used and check(cur, w):
                used.add(w)
                nxt = backtracking(w, cnt+1, mn)
                mn = min(mn, nxt)
                used.discard(w)
        
        return mn
    
    used = {begin}
    return backtracking(begin)

• 추가적으로 세 가지의 가지치기를 적용하여 TC #3에서 Solution 1.(0.49ms)에 비해 약 2.7배 빠르게(0.18ms) 동작하는 코드이다.

1. words에 target이 존재하지 않는다는 것은 결국 target으로 변환할 수 없다는 의미이므로, $O(n)$으로 존재 여부를 확인한 뒤 존재하지 않는다면 0을 return한다.
2. 알파벳의 개수가 2개 이상 다른 경우는 더이상 셀 필요 없이 단어 변환이 불가능한 경우이므로, 따로 함수를 만들어 조기종료한다. 이 때 반복문 종료 후의 cnt는 0 또는 1의 값을 가지므로 그대로 반환하면 1일 때 True, 0일 때 False를 나타내어 의도대로 동작한다.
3. 이번 단어를 변환했을 때의 변환 횟수가 현재까지 갱신한 최소 변환 횟수 이상이라는 것은 더이상 최솟값 갱신의 여지가 없으므로 조기종료한다.

---