[프로그래머스] 단어 변환 - 파이썬(python)

 

 

나의 풀이

step = []

def dfs(begin, target, words, cnt):
    
    if begin == target : 
        step.append(cnt)
        return
    
    for i in range(len(words)) :
        tmp = 0
        for j in range(len(words[i])) :
            if begin[j] == words[i][j] :
                tmp += 1
            if tmp == len(begin)-1 :
                lst = words[:]
                lst.remove(words[i])
                dfs(words[i], target, lst, cnt+1)    

def solution(begin, target, words):
    dfs(begin, target, words, 0)
    
    if step == [] : return 0
    else :
        step.sort()
        return step[0]

• 현재 단어에서 words 를 돌면서 문자 1개 빼고 일치한 단어를 찾으면, 그 단어를 begin 으로 하여 DFS 를 돌리는 방법으로 문제를 풀었다.
• 종료조건은 begin == target 으로, 이때는 step 이라는 리스트에 지금까지 변환된 개수를 추가하며 종료한다.
• 그렇지 않다면, 다시 words 를 돌면서 문자 1개 빼고 일치하는 단어 (변환할 수 있는 단어) 를 찾는다.
• 이때, 다음 dfs 에 들어가는 인자는 [begin -> 현재 문자에서 변활될 수 있는 단어 / lst -> 변환될 수 있는 단어를 제외한 words[] / cnt -> 1증가] 이다.
• 모든 dfs 가 종료되었으면, step 에는 begin -> target 으로 변환된 모든 경우의 수에 대해 변환에 걸린 단계가 추가되어있을 것이다. 따라서, step 을 오름차순으로 정렬하고 최솟값인 0번째 인덱스를 리턴해준다.
• 만약, step 이 비어있다면, target 에 도달할 수 없음을 의미하므로 0을 리턴한다.