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

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

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

 

ans=10000
def dfs(count, now, target, words, history):
    global ans
    if now == target:
        ans=min(ans, count)
        return
    else:
        if len(history)==len(words):
            return
        else:
            pos_word=[]
            for word in words:
                s_count=0
                if not word in history:
                    for w in range(len(word)):
                        if word[w]==now[w]:
                            s_count+=1
                        if s_count==len(word)-1:
                            pos_word.append(word)
            for word in pos_word:
                history.append(word)
                dfs(count+1, word, target, words, history)

def solution(begin, target, words):
    dfs(0,begin,target, words,[])
    if ans==10000:
        return 0
    return ans



begin="hit"
target="cog"
words=["hot", "dot", "dog", "lot", "log", "cog"]
print(solution(begin, target, words))