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

프로그래머스 문제 풀이 - 깊이/너비 우선 탐색 (DFS/BFS)

📰 문제

문제 확인 🏃

💡 입출력 예제

"hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]

>> 4

"hit", "cog", ["hot", "dot", "dog", "lot", "log"]

>> 0	# target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

💬 풀이

🎵 첫번째 풀이

answer = float('inf')

def solution(begin, target, words):
    
    if target not in words:
        return 0
    
    visited = [False] * len(words)
    
    find(words, visited, begin, target, 0)

    return answer

def find(words, visited, begin, target, count):

    if begin == target:
        global answer
        answer = min(answer, count)
        return

    for idx in range(len(words)):
        if not visited[idx] and check(begin, words[idx]):
            visited[idx] = True
            find(words, visited, words[idx], target, count+1)
            visited[idx] = False

def check(word1, word2):
    count = 0
    for i in range(len(word1)):
        if word1[i] is not word2[i]:
            count += 1
    return True if count == 1 else False

✒️ 생각