코딩 테스트/문제 풀기
[프로그래머스] 단어 변환
hazel_
2021. 4. 19. 20:58
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))