[프로그래머스 Lv3, python] - 단어 변환

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

프로그래머스

# 내 풀이(dfs)
min_res = float('inf')

def dfs(stand,target,cnt,visited,words):
    global min_res
    if stand == target:
        min_res = min(min_res,cnt)
    if cnt > len(words): # 깊이 벗어남
        return
    for i in range(len(words)):
        diff = 0
        if not visited[i]: # 방문 X
            for t in range(len(stand)):
                if stand[t] != words[i][t]:
                    diff += 1
            if diff == 1:# 1개만 다름
                visited[i] = True
                dfs(words[i],target,cnt+1,visited,words)
                visited[i] = False

        

def solution(begin, target, words):
    answer = 0
    visited = [False]*len(words)
    if target not in words: # 단어안에 없으면
        return 0
    dfs(begin,target,0,visited,words)
    if min_res == float('inf'):
        return 0
    return min_res

# bfs 사용

from collections import deque

def solution(begin, target, words):
    if target not in words:
        return 0
    
    visited = [False] * len(words)
    queue = deque([(begin, 0)]) # 기준, 횟수
    
    while queue:
        current, cnt = queue.popleft()
        
        if current == target: # 같으면 리턴! (최소임)
            return cnt
        
        for i in range(len(words)):
            if not visited[i]: # 방문 X
                diff = 0
                
                for j in range(len(current)):
                    if current[j] != words[i][j]: # 다른가?
                        diff += 1
                
                if diff == 1: # 다른게 한개임 => 방문
                    visited[i] = True
                    queue.append((words[i], cnt + 1)) # 기준을 갱신, 횟수+1
    
    return 0