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

 

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

<풀이>

• 재귀함수를 사용하여 DFS를 적용하였다.
• 철자가 하나만 다른 단어인지 확인하는 함수 canChange를 정의하였다.
• 현재 answer보다 함수 스택인 k가 크다면 바로 반환한다.
• 현재 dfs 함수에서의 cur_word와 target이 같다면 answer에 k를 할당한다.
• words를 반복하여 이미 바꾼 단어이거나 canChange가 True를 반환한다면 새로운 dfs함수를 호출한다.

def solution(begin, target, words):
    global answer
    answer = 0xffffff
    lew_b = len(begin)
    def canChange(first, second):
        diff = 0
        for i in range(lew_b):
            if first[i] != second[i]:
                diff += 1
 
            if diff > 1:
                return False
        if diff == 1:
            return True
        return False
    len_w = len(words)
    visited = [0 for _ in range(len_w)]
    
    def dfs(cur_word, k):
        global answer
        if k > answer:
            return
        
        if cur_word == target:
            answer = k
            return
        
        for w in range(len_w):
            if not visited[w] and canChange(cur_word, words[w]):
                visited[w] = 1
                dfs(words[w], k + 1)
                visited[w] = 0
    dfs(begin, 0)
    if answer == 0xffffff:
        answer = 0
    return answer