프로그래머스 단어 변환 코드 및 해설 (파이썬)

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

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

💡 begin에서 target으로 변환될 수 있는지 확인하는 것이 아니라, 거꾸로 target에서 한 알파벳씩 변환하면서 begin으로 변환될 수 있는지 확인합니다.

 

먼저 words 안에 target이 없다면 절대 begin이 target으로 변환될 수 없으므로 0을 반환하게 합니다.

 

words안에 target이 있다면, answer라는 리스트를 만들어 target이 begin으로 변환되는데 필요한 단계 수를 저장합니다.

 

search 함수를 통해 target에서 한 알파벳만 바꾸면서 begin으로 변환될 수 있는지 확인합니다.

 

우선 words 안의 단어 하나씩을 word라는 변수로 꺼낸 후, 이 word가 target과 같고, begin과 한 알파벳만 다른 사이라면 현재 depth를 answer에 추가합니다.

 

그렇지 않고 word가 target가 한 알파벳만 다른 사이라면 다시 recursive하게 search 함수를 호출하고 이때 target은 현재 word로, words는 words에서 현재 target을 제외한 리스트로, depth는 기존보다 1을 더한 값으로 줍니다.

이렇게 search 함수를 처음에 문제에 주어진 target, words를 넣고 depth는 1로 준 이후 이 과정에서 채워진 answer의 값 중 최솟값을 반환합니다.

 

# query와 key가 한 알파벳만 다른 사이면 True, 아니면 False 
def checkdiff1(query, key):
    diff = 0
    for a,b in zip(query,key):
        if a != b:
            diff += 1 
    return diff == 1 

def solution(begin, target, words):
    answer = []
    
    # words에 target 단어가 없으면 begin을 target으로 반환할 수 없으므로 0 반환 
    if target not in words:
        return 0

    # target에서 한 알파벳씩만 바꾸면서 begin으로 갈 수 있는지 확인 
    def search(target, words, depth):
        for word in words:
            # target 단어 자체가 한 알파벳만 바꾸면 begin이 되는 경우 
            if word == target and checkdiff1(begin, word):
                # 현재 depth를 answer에 추가 
                answer.append(depth)
            # words 안의 단어 중 target과 한 알파벳만 다른 사이인 경우 
            elif checkdiff1(target, word):
                # depth를 하나 더 늘려서 target 제외한 words 리스트에서 한 알파벳만 다른 사이들을 다시 search 
                search(word, [w for w in words if w != target], depth+1) 
        
    search(target, words, 1)
    
    # answer의 값 중 최솟값을 반환 
    return min(answer)