[프로그래머스/Python] 단어 변환 - Level3

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

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

이 문제는 최소 변환 수를 찾는 거였어서 BFS 문제인 줄 알았으나 코드를 짜다보니 DFS 문제였다. 책에서 DFS 문제는 재귀함수로 풀라고 되어 있어서 재귀함수만 생각하다보니까 잘 생각이 안났다.. 다른 사람의 코드를 보니 스택을 이용한 코드가 많았다. 쉽게 이해되는 코드를 참고해서 이해했다.

def solution(begin, target, words):
    if target not in words: # 변환할 수 없는 경우
        return 0

    visited = [0] * len(words) # 방문 여부를 저장하는 리스트
    answer = dfs(begin, target, words, visited) # dfs 수행
    
    return answer

# dfs 수행 메서드
def dfs(begin, target, words, visited):
    answer = 0 # 변환 횟수
    stacks = [begin] # 스택
    
    while stacks:
        stack = stacks.pop() # 비교할 기준 값
        
        if stack == target: # 기준값과 타겟이 같다면 answer 리턴
            return answer
        
        for i in range(len(words)):
            # 한글자만 다른 값을 찾으면
            if len([j for j in range(len(words[i])) if words[i][j] != stack[j]]) == 1:
                
                if visited[i] != 0: # 이미 방문했으면 넘어가기
                    continue
                    
                visited[i] = 1 # 방문한 값으로 바꾸기
                stacks.append(words[i]) # 스택에 값 추가
                
        answer += 1 # 변환 횟수 갱신
        
    return answer

visited 는 방문 여부를 저장하는 리스트로 값이 0 이면 방문하지 않은 상태이고, 값이 1 이면 방문한 상태이다. dfs 를 수행하는 메서드를 따로 정의한 후 dfs 메서드를 호출한다. 스택에 값이 없을 때까지 변환 횟수를 구한다. 한글자만 다른 값이면서 아직 방문하지 않은 값이라면 방문 여부 값을 1로 바꾸고 stacks 에 추가한 후 변환 횟수를 갱신한다. 이 과정을 반복한 후 스택에 값이 없으면 while 문을 빠져나와 answer 를 리턴한다.