본문 바로가기
코딩 테스트/문제 풀기

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

by hazel_ 2021. 4. 19.

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

 

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

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수

programmers.co.kr

 

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))

댓글