단어변환

단어 변환
깊이/너비 우선 탐색(DFS/BFS) 
4024명 완료

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

코딩테스트 연습 - 단어 변환

https://comdoc.tistory.com/entry/%EB%8B%A8%EC%96%B4%EB%B3%80%ED%99%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC?category=800088

단어변환 (파이썬)

정석적인 풀이는 bfs의 응용인 최단거리찾기일 것 같다. 

def solution(begin, target, words):
    def match(word1, word2):
        return sum(1 for char1, char2 in zip(word1, word2) if char1 != char2) == 1

    def bfs():
        queue, visited, path_, found_target_ = [begin], {begin}, {}, False
        while queue and not found_target_:
            v = queue.pop(0)
            for w in words:
                if w not in visited and match(v, w):
                    visited.add(w)
                    queue.append(w)
                    path_[w] = v
                    if w == target:
                        found_target_ = True
                        break
        return found_target_, path_

    found_target, path = bfs()
    if not found_target:
        return 0
    count = 0
    while target != begin:
        target = path[target]
        count += 1
    return count