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

😄 아이디어

1. words내 사용된 단어를 알파벳으로 변환하고 set 형태로 관리해, 변환 경우의 수를 최소화한다.

2. begin으로 DFS 시작, 변수로 주어진 단어는 첫 알파벳부터 set내의 글자로 바꿔가며 words내 존재확인

3. 존재하는 경우 visited의 값을 방문한 것으로 바꿔주고 다음 DFS 실행

4. 값이 최소값으로 변경되었다면 그대로 반환, 아니라면 0으로 반환

answer = 1_000_000_000

def solution(begin, target, words):
    global answer
    
    charset = set(char for word in words for char in word)
    visited = [0 for _ in words]
    count = 0
    dfs(begin, charset, count, visited, target, words)
    
    if answer == 1000000000:
        answer = 0
    return answer

def dfs(word, charset, count, visited, target, words):
    if word == target:
        global answer
        answer = min(answer, count)
        return
    
    for c in charset:
        for i in range(0, len(word)):
            l = list(word)
            l[i] = c
            conv = ''.join(l)
            
            if conv in words and visited[words.index(conv)] == 0:
                visited[words.index(conv)] = 1
                dfs(conv, charset, count + 1, visited, target, words)
                visited[words.index(conv)] = 0
PYTHON

✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43163