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

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

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

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

 

풀이 : dfs (stack)

def solution(begin, target, words):
    answer = 0 # depth
    stacks = [begin] # dfs
    visited = []
    
    if target not in words:
        return 0
    
    while stacks:
        print("while문 stacks", stacks)
        print("while문 visited", visited)
        
        stack = stacks.pop()
        if stack == target:
            return answer
        
        for word in words:
            diff = 0
            print("for문 word : ", word)
            # begin과 target의 각 인덱스를 비교하여 다른 글자갯수가 1인 것을 stack에 넣는다.
            if word not in visited:
                for i in range(len(word)):
                    if stack[i] != word[i]:
                        diff = diff + 1
                if diff == 1:
                    stacks.append(word)
                    visited.append(word)
                    
                    
        answer = answer + 1
        
    
    return answer

1. words 배열에 target이 없을 경우 0 리턴

2. words 배열을 순회하며 begin과 알파벳 차이가 1인 단어들을 스택으로 삽입

3. 스택에 내용이 없어질 때까지 순회하며 target이 아니면 반복합니다. 

 

 재귀에서 begin을 업데이트 하는 방식으로 해보려다가 자꾸 생각이 끊겨 스택을 사용했습니다. (간지나는 재귀함수 사용하고 싶다..) 처음엔 dfs를 사용해서 각 visited 방법에 따라 count를 센 뒤 min(list)를 하려고 했습니다. 

 하지만 위 코드에서는 굳이 최소 횟수를 비교하지 않아도 된다고 생각했습니다. 왜냐하면 while문을 돌며 stack에 있는 값들을 모두 도는데 한번 반복할 때마다 answer은 계속 증가하므 stack == target일 때가 최소의 횟수가 되기 때문입니다. 흠.. dfs에 대해 공부해야 할 것 같습니다요 ㅠ

 

# 결과