[PG/Python] 단어 변환

📌 문제

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

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

 

📌 문제 접근 방법

1. dfs를 사용하여 풀이하였고, 스택에 변환 횟수를 같이 저장해주었다.
2. 만약 target 단어가 words에 없다면 바로 0을 리턴한다.
3. words에 target이 있다면 스택에서 하나씩 pop하여 words에 있는 단어와 비교한다.
4. words의 단어와 딱 한 글자만 다른 단어를 다시 스택에 넣는다.
5. 위의 과정을 반복하다가 스택에서 pop한 단어가 target과 일치하면 그 때의 변환 횟수를 출력한다.

 

📌 코드

def solution(begin, target, words):
    if target not in words:
        return 0
    
    stack = [(begin, 0)]
    visited = [0 for _ in range(len(words))]
    N = len(begin)
    
    while stack:
        word, cnt = stack.pop()
        if word == target:
            return cnt
        
        for i in range(len(words)):
            if not visited[i]:
                c = 0
                for j in range(N):
                    if word[j] != words[i][j]:
                        c += 1
                
                if c == 1:
                    visited[i] = 1
                    stack.append((words[i], cnt+1))